牛客寒假营

牛客寒假营

I

题意：
就是给你n个物品，有攻击和消耗。可以选择一些物品，当消耗的总和是m的倍数的时候，攻击总和的最大值是多少。

思考：
刚开始看了看，感觉是map题，实际上不是。然后想到以前的那个两个数加在一起是m的倍数啥的，就想到了%m。妈的，然后总想着是两个数组合在一起，然后贪心这样做，错了几次。然后发现不对，应该是dp，那这就和之前做过的几次数字类dp很像，但是又出问题了，初始化的时候没考虑当前dp的定义是啥，当前余数是恰好为m的时候，所以初始化除了00，别的都要是非法状态。
其实也可以先把所有的数取余之后，把消耗的能量加起来为ans，那么就是背包容量为ans的，01背包，dp含义定义为消耗能量恰好为j的时候的最大值。然后最后再遍历一遍ans，当且仅当i是m的倍数的时候可以更新答案。

代码：

int T,n,m,k;
PII va[N];
int dp[M][M];signed main()
{IOS;cin>>n>>m;for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;for(int i=1;i<=n;i++) va[i].fi %= m;mem(dp,-0x3f);dp[0][0] = 0;for(int i=1;i<=n;i++){for(int j=0;j<m;j++) dp[i][j] = dp[i-1][j]; //如果不选for(int j=0;j<m;j++) //这些状态如果选,去更新可以选的状态dp[i][(va[i].fi+j)%m] = max(dp[i][(va[i].fi+j)%m],dp[i-1][j]+va[i].se);}if(dp[n][0]==0) cout<<-1;else cout<<dp[n][0];return 0;
}

总结：
别太慌，思考好再交题。