竞赛真理题解(分组背包做法)

题面

既然是分组背包,那么一定要分组。

我们可以考虑这样分:
局部截取_20250202_195244

这样,就分成了 n 组,每组有 2 个物品。

这是分组背包的核心代码:

for(int i=1;i<=t;i++)for(int j=v;j>=0;j--)for(int k=0;k<(int)w[i].size();k++)if(j>=w[i][k])dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);

可以发现,其中(int)w[i].size()就是每一组物品的个数,但我们已经明确了每一组的物品个数为 2 ,就可以简化一下:

for(int i=1;i<=t;i++)for(int j=v;j>=0;j--)for(int k=0;k<2;k++)if(j>=w[i][k])dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);

如果再把for(int k=0;k<2;k++)转换一下(因为并没有用vector存分数和时间),就可以展开成这样:

if(j>=t1[i])dp[j]=max(dp[j],dp[j-t1[i]]+w1[i]);
if(j>=t2[i])dp[j]=max(dp[j],dp[j-t2[i]]+w2[i]);

最终就变成了这样:

for(int i=1;i<=n;i++)
    for(int j=t;j>=0;j--){
        if(j>=t1[i])dp[j]=max(dp[j],dp[j-t1[i]]+w1[i]);
        if(j>=t2[i])dp[j]=max(dp[j],dp[j-t2[i]]+w2[i]);
    }
给想抄题解的人一句话

局部截取_20250202_200440

这么努力!我都懒得写题解了 qwq

我能写题解就写,不能写题解就不写

%%%好勤奋

看不太懂啊 :smiling_face_with_tear: :smiling_face_with_tear: :smiling_face_with_tear:

因为这是普及组的

这道题我们基础组也有啊

image

如果我没记错的话,正解应该是背包dp

dui

@路漫漫其修远兮_蒟蒻将上下而求索 问一下你们普及有《金明的预选方案》这道题目吗?

没有,但有image

@路漫漫其修远兮_蒟蒻将上下而求索 o那就算了,开心的金明一道模板题也挺简单