转载

完全背包变型题（hdu5410)

这是2015年最后一场多校的dp题，当时只怪自己基础太差，想了1个多小时才想出来，哎，9月份好好巩固基础，为区域赛做准备。题目传送门

完全背包变型题（hdu5410)

题目的意思是给你n元钱，m类糖果，每类糖果分别有p, a, b, p表示单价，假设付了w*p元，那么他能获得a*w + b个糖果。求最大的糖果数。

当时一看到这题，觉得是完全背包,设dp[i][j]表示买到第i件物品的时候已经花了j元钱，所得到的最多的糖果数。

很容易想到转移方程为：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * p] + a * k + b);(k > 0 && k * p <= j)

当信心十足准备敲的时候才忽然发现时间复杂度为O（n^3), 而n 最大为1000，毫无疑问会超时。怎么办？

然后我们就想我们用01背包的思维去想这题，就可以把它优化到O（n^2)了；然后突然又发现一个问题，因为多了个b，发现处理的时候要考虑是否是第一次买，那么我们就开个vis数组来表示有无买过，1表示买过，0表示没有。

附上总代码：

 1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 using namespace std;  5   6 const int N = 2000 + 5;  7   8 int T, n, m;  9  10 int p[N], a[N], b[N]; 11  12 int vis[N][N], dp[N][N]; 13  14 void work(){ 15     memset(dp, 0, sizeof(dp)); 16     memset(vis, 0, sizeof(vis)); 17     for(int i = 1; i <= n; i ++){ 18         for(int j = 0; j <= m; j ++){ 19             dp[i][j] = dp[i - 1][j]; 20             if(j >= p[i]){ 21                 int t = dp[i][j - p[i]] + a[i]; 22                 if(!vis[i][j - p[i]]) t += b[i]; 23                 int t1 = dp[i - 1][j - p[i]] + a[i] + b[i]; 24                 if(t1 > t) t = t1; 25                 if(t > dp[i][j]){ 26                     dp[i][j] = t; 27                     vis[i][j] = 1; 28                 } 29             } 30         } 31     } 32     printf("%d/n", dp[n][m]); 33 } 34  35 int main(){ 36     scanf("%d", &T); 37     while(T--){ 38         scanf("%d%d", &m, &n); 39         for(int i = 1; i <= n; i ++) scanf("%d%d%d", p + i, a + i, b + i); 40         work(); 41     } 42     return 0; 43 }