SRM563 Div1 Medium

500

DP[どこまで見たか][何枚めくったか] = 最適値
そこまで難しくは無い割に面白い問題でした。

view plainprint?

1. class SpellCards {  
2. public:  
3.   int maxDamage(vector <int> level, vector <int> damage)  
4.   {  
5.     const lli inf = 1 << 29;  
6.     const int N = 50 + 5;  
7.     const int M = 50 * 50 + 51;  
8.     int dp[N][M];  
9.     fill(&dp[0][0], &dp[N - 1][M - 1] + 1, -inf);  
10.     dp[0][0] = 0;  
11.   
12.     for (int nth = 0; nth < level.size(); ++nth) {  
13.       for (int flip = 0; flip < M; ++flip) {  
14.         dp[nth + 1][flip] = max(dp[nth + 1][flip], dp[nth][flip]);  
15.         int l = level[nth];  
16.         dp[nth + 1][flip + l] = max(dp[nth + 1][flip + l], dp[nth][flip] + damage[nth]);  
17.       }  
18.     }  
19.     int mx = 0;  
20.     for (int i = 0; i <= level.size(); ++i) {  
21.       mx = max(mx, dp[level.size()][i]);  
22.     }  
23.     return mx;  
24.   }  
25. };  

class SpellCards {
public:
  int maxDamage(vector <int> level, vector <int> damage)
  {
    const lli inf = 1 << 29;
    const int N = 50 + 5;
    const int M = 50 * 50 + 51;
    int dp[N][M];
    fill(&dp[0][0], &dp[N - 1][M - 1] + 1, -inf);
    dp[0][0] = 0;

    for (int nth = 0; nth < level.size(); ++nth) {
      for (int flip = 0; flip < M; ++flip) {
        dp[nth + 1][flip] = max(dp[nth + 1][flip], dp[nth][flip]);
        int l = level[nth];
        dp[nth + 1][flip + l] = max(dp[nth + 1][flip + l], dp[nth][flip] + damage[nth]);
      }
    }
    int mx = 0;
    for (int i = 0; i <= level.size(); ++i) {
      mx = max(mx, dp[level.size()][i]);
    }
    return mx;
  }
};