三年目の初学者(7問目)

問題
topcoder SRM 602 div1 easy
TopCoder Statistics - Problem Statement

使用言語
C++

方針
・全探索
(・dp)

所感
・いけるもんだと思っていた。実行するまでは

問題点と解決案(解決してない)
・O(2^n)で大変
・一部ケースでTLEになったため、残りの全てのコンテストで勝ったとしても2200を超えない(brown coderにならない)場合はすぐに0を返すようにした。
・実行時間が少し減少したが、一部TLEのまま
・できたら追記します

コード

//status: true->brown, false->ciel
int cc (int rate, int i, vector<int> D, int size, bool status, vector<int> dp)
{
  if (i == size) return 0;

  if (status) {
    return (rate - D[i] < 2200)
            ? cc(rate - min(rate, D[i]), i+1, D, size, false, dp) + 1 : -INF;
  } else {
    if (rate + dp[i] < 2200) return 0;

    int r = rate + D[i];
    bool status_p = (r >= 2200);
    return max(cc(r, i+1, D, size, status_p, dp) + (int) status_p,
            cc(rate - min(rate, D[i]), i+1, D, size, false, dp));
  }
}

class TypoCoderDiv1 {
    public:
    int getmax(vector<int> D, int X) {
      int size = D.size();

      vector<int> dp(51, 0);
      for (int i = size - 1; i >= 0; i--) {
        dp[i] = dp[i+1] + D[i];
      }

        return cc(X, 0, D, size, X >= 2200, dp);
    }
};