洛谷P1064 金明的预算方案(01背包变形)

深藏阁楼爱情的钟 2021-09-15 02:22 293阅读 0赞

链接:https://www.luogu.org/problemnew/show/P1064

遇到的第一个看起来难一点的01背包，主要是处理附件。开始想要通过是否有附件去切题，后来发现应该由主件来联系附件。

不如假设每个主件都有2个附件（没附件的为0），由主件联系附件，当是主件时，再去看附件的情况。然后写状态转移方程，由一个变成四个（其实并没有多很多）

五种选择

1.不选

2.只选这个主件

3.选这个主件，并且选附件1

4.选这个主件，并且选附件2

5.选这个主件，并且选附件1和附件2.

upd:树形dp会Tle(也许是我不会用QAQ)

upd:被部分题解坑了，树形dp能A，注意题目中的条件(价格都是10的整数倍);

//重要的是处理附件
    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,m,pp;
        int v[100],w[100],f[100],ff[32005][3];//f[]为是否为主件，ff[][]储存附件的位置
        int dp[32005];
        cin>>m>>n;
        memset(v,0,sizeof v);
        memset(w,0,sizeof w);
        memset(f,0,sizeof f);
        memset(ff,0,sizeof ff);
        memset(dp,0,sizeof dp);
        for(int i=1; i<=n; i++)
        {
            cin>>w[i]>>v[i]>>pp;
            v[i]*=w[i];
            if(pp)//为附件
            {
                f[i]=1;
                if(!ff[pp][1])//为附件1
                    ff[pp][1]=i;
                else
                    ff[pp][2]=i;
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=m; j>=w[i]; j--)
            {
                if(!f[i])//主件才进行
                {
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                    if(w[ff[i][1]]+w[i]<=j)
                        dp[j]=max(dp[j],dp[j-w[i]-w[ff[i][1]]]+v[i]+v[ff[i][1]]);
                    if(w[ff[i][2]]+w[i]<=j)
                        dp[j]=max(dp[j],dp[j-w[i]-w[ff[i][2]]]+v[i]+v[ff[i][2]]);
                    if(w[ff[i][1]]+w[ff[i][2]]+w[i]<=j)
                        dp[j]=max(dp[j],dp[j-w[i]-w[ff[i][1]]-w[ff[i][2]]]+v[i]+v[ff[i][1]]+v[ff[i][2]]);
                }
            }
        }
        cout<<dp[m]<<endl;
        return 0;
    
    }

题后感受：假如附件最多不为2，而是很大或未知，那就应该有一种更好的解法，然而我不会。（太菜了，这次校赛的dp一个都没写出来）