宝物筛选

凡是背包裸题,二进制随便套..

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=3e5+4e4;
int t[M],c[M],p[M];
int id,n;
int T[M],val[M];
int f[M];
inline void init()
{
    for(int i=1;i<=n;i++)
    {
        int vnt=1;
        while(true)
        {
            if(p[i]-vnt<0)
            {
                val[id]=c[i]*p[i];
                T[id]=t[i]*p[i];
                id++;
                break;
            }
            else
            {
                p[i]-=vnt;
                val[id]=c[i]*vnt;
                T[id]=t[i]*vnt;
                id++;
            }
            vnt*=2;
        }
    }
}

int main()
{
    int v;
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&c[i],&t[i],&p[i]);
    }
    init();
    for(int i=0;i<id;i++)
    {
        for(int j=v;j>=T[i];j--)
        {
            f[j]=max(f[j],f[j-T[i]]+val[i]);
        }
    }
    printf("%d\n",f[v]);
    return 0;
}