題目

就是一個英雄瞎搞之類為世界作出貢獻，藍后某zz公司免費給他糖，然后由于某些原因他只能拿能整除k數量糖果，然后每個盒子里有一定數量的糖果，拿了盒子就必須拿完里面所有的糖果，求他怎么拿的最多。

---

輸入

5 7
1
2
3
4
5

輸出

14

樣例解釋

Dzx的選擇是2+3+4+5=14，這樣糖果總數是7的倍數，并且是總數最多的選擇。

---

解題思路

emmmmmmmmmmmmmmmmmmmmmmm?其實我開始是用背包做的，但是數據忒大了QAQ。所以……
好吧，講正事
我們用f[i][j]表示前i個糖果數量%k余j時的最大值。藍后我們就可以醬紫做。一個是選擇這個糖，一個是不選這個（就是我不要這個了 ╯^╰ ）。
動態轉移方程：
f[i][(f[i-1][j]+a[i])%k]=max(f[i][(f[i-1][j]+a[i])%k],f[i-1][j]+a[i])

---

代碼

#include<cstdio> #include<iostream> using namespace std; int n,k,a[10001],m; int f[1001][1001]; int main() {scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) {scanf("%d",&a[i]);}//以上↑為輸入for (int i=1;i<=n;i++){for (int j=0;j<k;j++) f[i][j]=f[i-1][j];//全部初始化為這次不選糖for (int j=0;j<k;j++)f[i][(f[i-1][j]+a[i])%k]=max(f[i][(f[i-1][j]+a[i])%k],f[i-1][j]+a[i]);//選擇這個糖時求最優解。}printf("%d",f[n][0]);//輸出 }

總結

以上是生活随笔為你收集整理的OJ4008-糖果【各种dp之3】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。