GYM101673G（dp）

佚名 6年前 (2019-04-08) 随笔 1669人围观抢沙发百度已收录

dp[i][j][0/1]：第i天处于第j状态要不要吃。

const int maxn = 1e2 + 5;
int n, a[maxn], b[maxn];
int dp[maxn][maxn][2];

int main() {
    read(n), read(b[1]);
    rep(i, 1, n)    read(a[i]);
    rep(i, 2, n)    b[i] = b[i - 1] * 2 / 3;

    rep(i, 1, n) {
        rep(j, 1, i) {
            dp[i][j][0] = dp[i - 1][j + 1][0];
            dp[i][j][1] = dp[i - 1][j + 1][0] + min(a[i], b[j]);
            if (j >= 2) {
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - 1][1]);
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][1] + min(a[i], b[j]));
            }
            if (i > 3)  {
                dp[i][1][0] = max(dp[i][1][0], max(dp[i - 3][j][0], dp[i - 3][j][1]));
                dp[i][1][1] = max(dp[i][1][1], dp[i][1][0] + min(a[i], b[1]));
            }
            
        }
    }

    int ans = 0;
    rep(i, 1, n) {
        ans = max(max(dp[n][i][0], dp[n][i][1]), ans);
    }
    writeln(ans);
    return 0;
}