SRM563 Div1 Medium

500

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

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;
  }
};