SRM 563 DIV1 DIV2

2、0-1背包问题，边界问题稍微麻烦一些。

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <map>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <queue>
 9 #include <cmath>
10 using namespace std;
11 int dp[105][105];//dp[i][j],从第i个card开始，后边剩余j张牌的情况下最大的damage
12 class SpellCards {
13 public:
14     int maxDamage(vector<int> level, vector<int> damage) {
15         int dsz = damage.size();
16         int lsz = level.size();
17         int res = 0;
18 
19         for (int id = 0; id < dsz; id++) {
20             rotate(level.begin(), level.begin() + 1, level.end());
21             rotate(damage.begin(), damage.begin() + 1, damage.end());
22             memset(dp, -1, sizeof(dp));
23             
24             if (level[lsz - 1] == 1) {//初始化倒数第一个
25                 dp[lsz - 1][0] = damage[lsz - 1];
26             }
27             dp[lsz - 1][1] = 0;
28 
29             for (int i = lsz - 2; i > -1; i--) { //倒数第二个个位置开始
30                 for (int j = 0; j < lsz - i + 1; j++) {//后边还剩下j个可以用
31                     if (0 == j) { //初始化dp的值，表示不使用当前的card
32                         dp[i][j] = -1;
33                     } else {
34                         dp[i][j] = dp[i + 1][j - 1];
35                     }
36                     
37                     int use_need = level[i] - 1; //使用之后需要的个数
38                     if (dp[i + 1][j + use_need] != -1) {//如果可以使用
39                         dp[i][j] = max(dp[i][j],
40                                 dp[i + 1][j + use_need] + damage[i]);
41                         res = max(res, dp[i][j]);
42                     }
43                 }
44             }
45         }
46         return res;
47     }
48 };

递归版本

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <map>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <queue>
 9 #include <cmath>
10 using namespace std;
11 int dp[105][105];//dp[i][j],从第i个card开始，后边剩余j张牌的情况下最大的damage
12 class SpellCards {
13 public:
14     int rec(vector<int>& level, vector<int>& damage,int cur,int need,int total){
15         int &res=dp[cur][need];
16         if(-1==res){
17             if((cur+need)==total){
18                 res=0;
19             }else{
20                 res=rec(level,damage,cur+1,max(need-1,0),total);//不使用
21                 if((cur+need+level[cur])<=total){//使用
22                     res=max(res,damage[cur]+rec(level,damage,cur+1,need+level[cur]-1,total));
23                 }
24             }
25         }
26         return res;
27     }
28     int maxDamage(vector<int> level, vector<int> damage) {
29         int dsz = damage.size();
30         int lsz = level.size();
31         int res = 0;
32 
33         for (int id = 0; id < dsz; id++) {
34             rotate(level.begin(), level.begin() + 1, level.end());
35             rotate(damage.begin(), damage.begin() + 1, damage.end());
36             memset(dp, -1, sizeof(dp));
37             res = max(res, rec(level,damage,0,0,lsz));
38         }
39         return res;
40     }
41 };

最高效方法：http://www.cppblog.com/hanfei19910905/archive/2012/12/09/196119.aspx

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <map>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <queue>
 9 #include <cmath>
10 using namespace std;
11 int dp[55];
12 //dp[i]当前有i张牌的情况下的最大的damage
13 int work(vector<int> a, vector<int> d) {
14     int n = a.size(), ans = 0;
15     memset(dp, -1, sizeof(dp));
16     dp[0] = 0;
17     for (int j = n - 1; j > -1; j--) {
18         for (int i = n; i; i--)
19             if (i - a[j] >= 0) {
20                 int v = i - a[j];
21                 if (dp[v] == -1)
22                     continue;
23                 dp[i] = max(dp[i], dp[v] + d[j]);
24                 ans = max(ans, dp[i]);
25             }
26     }
27     return ans;
28 }
29 class SpellCards {
30 public:
31     int maxDamage(vector<int> level, vector<int> damage) {
32         return work(level, damage);
33     }
34 };