#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 32005, MAXM = 65;
vector<vector<int>> price(MAXM, vector<int>(3, 0)), satis(MAXM, vector<int>(3, 0)); // price: [i][0,1,2] = self, acce1, acce2.., satisfaction = price * significance
vector<vector<int>> dp(MAXM, vector<int>(MAXN, 0)); // expend all money

int main()
{
    int m, N;
    cin >> N >> m;
    for (int i = 1 ; i <= m ; ++ i)
    {
        int v, p, q;
        cin >> v >> p >> q;
        if (q == 0)
        {
            price[i][0] = v;
            satis[i][0] = v * p;
        }
        else
        {
            int nCnt = 1;
            while (price[q][nCnt] != 0 and (nCnt < 2) ) nCnt++; // find next avail empty accessory
            price[q][nCnt] = v;
            satis[q][nCnt] = v * p;
        }
    }
    for (int i = 1 ; i <= m ; ++ i)
    {
        for (int j = 0 ; j < price[i][0] ; ++ j) dp[i][j] = dp[i - 1][j]; // !!! update status
        for (int j = price[i][0] ; j <= N ; ++ j) 
        {
            int a = price[i][0], b = price[i][1], c = price[i][2];
            int d = satis[i][0], e = satis[i][1], f = satis[i][2];
            
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + d); // pick main or not

            if (j >= (a + b)) dp[i][j] = max(dp[i][j], dp[i - 1][j - a - b] + d + e); // pick main and acc1 or not
            if (j >= (a + c)) dp[i][j] = max(dp[i][j], dp[i - 1][j - a - c] + d + f); // pick main and acc2 or not
            if (j >= (a + b + c)) dp[i][j] = max(dp[i][j], dp[i - 1][j - a - b - c] + d + e + f); // pick all 3
        }
    }
    cout << dp[m][N] << endl;
    return 0;
}

关键思路

其实确实是挺简单的,前面几次尝试越改越复杂了,最后自己都晕了.

关键在于预处理和捆绑法.

  • 预处理

    • 预处理能很大的节省代码量同时也方便debug,理清思路.

    预处理的作用就是把题目中的主体与附件捆绑放在一起(我这里是放在一个数组里),题目中说最多只有两个附件,故只需要三个位置(三个数组单元)就够用了,同时把所有捆绑在一起的主体与附件再捆绑成一个大的二维数组(即代码中的price和satis).同时满意度也在预处理中提前计算出来了.

  • 状态转移

捆绑完成后就是一个01背包的问题,只是转移方程多了几个量而已,总共有五种可以转移到当前状态的状态

  1. 不拿
  2. 拿主体
  3. 拿主体+拿附件1
  4. 拿主体+拿附件2
  5. 拿主体+1+2

取其中最大值就是此决策的的最优解.

注意

数组赋初值0是因为,题目没有要求钱必须花完,所以什么都不买的0也是一种合法状态.

我这题用的01背包的二维数组组解决办法(未优化空间)要记得把上一次的状态更新下来.

我的错误

在状态转移方程的实现上,我最后的循环如果是判断条件不满足(比如没有附件或者钱不够)则continue,继续下次循环则无法通过最后一个输入

但如果改成条件满足则执行相应的状态转移则可以通过.

这两个代码的关键在于一个跳过了下面的其他转移,另一个都试了一遍.

我开始的想法是,我前面的预处理是按序的从0~2填值,如果前面的不满足比如没钱或者没有附件则后面的也肯定不满足.

但是实际上,不同附件的价格是不一样的,也不是按序的.举个例子,如果,刚好有两个附件,如果前面一个买不起跳过了后面可能买得起的则就会漏掉最优解,所以得都试一遍,又或者说状态转移方程的代码实现就是得一个个试取最大值,不要自作聪明.

免责

这题我刚了很久越想越气就写了个思路,纯属个人理解仅供参考,有纰漏望海涵与指出,有参考网上dl思路时间有限就不一一指出,在此表示感谢.