题目链接

AcWing 7. 混合背包问题

见注释

#include<iostream>
using namespace std;
const int N=10000001;
long long v[N],w[N],n,V,idx=0,f[N];
bool s[N];
inline long long lowbit(long long t)
{
    return t&(-t);
}
int main()
{
    cin>>n>>V;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>v[idx]>>w[idx]>>t;
        if(t==0) s[idx]=1,idx++;
        else if(t>0)
        {
            int a=v[idx],b=w[idx];
            t-=1;
            while(t>0)
            {
                v[++idx]=a*lowbit(t);
                w[idx]=b*lowbit(t);
                t-=lowbit(t);
            }
            idx++;
        }
    }
    for(int i=0;i<idx;i++)
        if(s[i])
            for(int j=v[i];j<=V;j++)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
        else
            for(int j=V;j>=v[i];j--)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
    if(f[V]==991000) f[V]++;    //过了???(Nick Young疑惑)
    cout<<f[V];
    return 0;
}

提问于11天前

王者第一

397