问题描述

小 X 确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，小 X 需要挑选一些在路上使用的物品，但他只有一个能装体积为 m 的背包。显然，背包问题对小 X 来说过于简单了，所以他希望你来帮他解决这个问题。
小 X 可以选择的物品有 n 样，一共分为甲乙丙三类：
1.甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，v(x) = A*x^2-Bx，A，B 是每个甲类物品的两个参数。注意每个体积的甲类物品只有一个。
2.乙类物品的价值 A 和体积 B 都是固定的，但是每个乙类物品都有个参数
C，表示这个物品可供选择的个数。
3.丙类物品的价值 A 和体积 B 也是固定的，但是每个丙类物品可供选择的个数都是无限多个。
你最终的任务是确定小 X 的背包最多能装有多大的价值上路。

输入文件

第一行两个整数 n，m，表示背包物品的个数和背包的体积；
接下来 n 行，每行描述一个物品的信息。第一个整数 x，表示物品的种类： 若 x 为 1 表示甲类物品，接下来两个整数 A, B，为 A 类物品的两个参数； 若 x 为 2 表示乙类物品，接下来三个整数 A，B，C。A 表示物品的价值，B
表示它的体积，C 表示它的个数；
若 x 为 3 表示丙类物品，接下来两个整数 A，B。A 表示它的价值，B 表示它的体积。

输出文件

输出文件仅一行为一个整数，表示小 X 的背包能装的最大价值。

样例输入

4 10
2 1 2 1
1 1 2
3 5 2
2 200 2 3

样例输出

610

数据范围

对于 50%的数据，只有乙和丙两类物品；
对于 70%的数据，1<=n<=100, 1<=m<=500，0<=A,B,C<=200； 对于 100%的数据，1<=n<=100, 1<=m<=2000，0<=A,B,C<=200；

#include<iostream>
#include<cstdio>

using namespace std;

struct record{
    int x,a,b,c;
};

int n,m,ans;
int f[2001];
record thing[101];

int main(){
    freopen("pack.in","r",stdin);
    freopen("pack.out","w",stdout);
    int i,j,k;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%d",&thing[i].x);
        if (thing[i].x==2)
            scanf("%d%d%d",&thing[i].a,&thing[i].b,&thing[i].c);
            else
                scanf("%d%d",&thing[i].a,&thing[i].b);
    }
    for (int i=1;i<=n;i++){
        if (thing[i].x==1){
            for (j=m;j>=thing[i].b;j--)
                for (k=thing[i].b;k<=j;k++)
                    f[j]=max(f[j],f[j-k]+thing[i].a*k*k-thing[i].b*k);
        }
        if (thing[i].x==2){
            for (j=m;j>=thing[i].b;j--)
                for (k=1;k<=min(j/thing[i].b,thing[i].c);k++)
                    f[j]=max(f[j],f[j-k*thing[i].b]+k*thing[i].a);
        }
        if (thing[i].x==3){
            for (j=m;j>=thing[i].b;j--)
                for (k=1;k<=j/thing[i].b;k++)
                    f[j]=max(f[j],f[j-k*thing[i].b]+k*thing[i].a);
        }
    }
    ans=f[0];
    for (i=1;i<=m;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}//100