【洛谷P2623物品选取】动态规划

分析

各种背包弄在一起。

AC代码

// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

#define ms(a,b) memset(a,b,sizeof(a))

typedef long long ll;

int f[2005];

int n,m;

inline int read() {

    int x=0,w=0; char ch=0;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return w?-x:x;

}

inline void write(int x) {

     if(x<0) putchar('-'),x=-x;

     if(x>9) write(x/10);

     putchar(x%10+'0');

}

int main(int argc,char* argv[]) {

    std::ios::sync_with_stdio(false);

    n=read(),m=read();

    while (n--) {

        int opt=read(),a,b,c;

        switch (opt) {

            case 1:

                a=read(),b=read();

                for (int i=m;i;i--)

                    for (int j=1;j<=i;j++)

                        f[i]=max(f[i],f[i-j]+j*j*a-b*j);

                break;

            case 2:

                a=read(),b=read(),c=read();

                for (int i=m;i>=b;i--)

                    for (int j=1;j<=min(c,i/b);j++)

                        f[i]=max(f[i],f[i-j*b]+j*a);

                break;

            case 3:

                a=read(),b=read();

                for (int i=b;i<=m;i++) f[i]=max(f[i],f[i-b]+a);

                break;

        }

    }

    write(f[m]); puts("");

    return 0;

}