GYM 101673G（dp）

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;

}

巴特西

GYM 101673G（dp）

最新文章

热门文章