RdOI-R1 T3 冰淇淋游戏 题解

· · 个人记录

首先,我们要计算每一关可获得的最大分数:

因为被吃掉的冰淇淋一定是连续的,所以我们可以使 dp(i,j) 为吃掉区间 [i,j] 内所有冰淇淋可获得的最大分数。

状态转移方程如下:

dp(i,j)=max\{dp(i-1,j)+y_{k,i}\times (j-i+1), dp(i,j-1)+y_{k,j}\times (j-i+1)\}

边界条件为:dp(c_k,c_k)=y_{k,c_k}

计算完每一关可获得的最大分数,就可以"用多重背包"来计算最终答案了。 P.S.:别忘了考虑先决条件。 代码如下: ```cpp #include <cstdio> #include <cstring> #define INF 100000000 using namespace std; int dp[501][501], n, t, A[501], s, m, c, k, si[201], mi[201], win[100001], T[501], w = 0; int dp2[201]; long long ans = 0; inline int read() { int x = 0, f = 1; char c = getchar(); while (!('0' <= c && c <= '9')) { if (c == '-') f = -1; c = getchar(); } while ('0' <= c && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } long long max(long long a, long long b) { return a < b ? b : a; } struct sc1 { long long v; bool f; sc1(long long v = 0, bool f = 0) :v(v), f(f) {} }d[2][100001], sc[100001]; int dp1(int l, int r) { if (l == r && l == c) return A[c]; if (r < c || l > c) return -INF; if (dp[l][r] >= 0) return dp[l][r]; return dp[l][r] = max(dp1(l + 1, r) + (r - l + 1) * A[l], dp1(l, r - 1) + (r - l + 1) * A[r]); } bool SC(int i, int j, int r, long long value) { if (d[i][j].f > sc[r].f) return 1; if (value >= sc[r].v) return 1; return 0; } int main() { n = read(), t = read(); for (int i = 1; i <= n; i++) { memset(dp, -1, sizeof(dp)); memset(A, 0, sizeof(A)); s = read(), m = read(), k = read(), c = read(), mi[i] = m, si[i] = s; for (int j = 1; j <= k; j++) A[j] = read(); dp2[i] = dp1(1, k); T[i] = T[i - 1] + si[i]; } for (int i = 0; i <= t; i++) d[0][i].f = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= t; j++) d[w ^ 1][j] = sc1(0, 0); if (mi[i] > t / si[i]) mi[i] = t / si[i]; for (int b = 0; b < si[i]; b++) { int l = 1, r = 2; sc[1] = d[w][b]; win[1] = 0; for (int k = 1; k <= (t - b) / si[i]; k++) { if (k * si[i] + b < T[i - 1]) continue; while (l < r && (k - win[l]) > mi[i]) l++; if (l < r && d[w ^ 1][k * si[i] + b].v < sc[l].v + 1ll * k * dp2[i] && sc[l].f) d[w ^ 1][k * si[i] + b] = sc1(sc[l].v + 1ll * k * dp2[i], sc[l].f); long long tmp = d[w][k * si[i] + b].v - 1ll * k * dp2[i]; while (l < r && SC(w, k * si[i] + b, r - 1, tmp)) r--; sc[r] = sc1(tmp, d[w][k * si[i] + b].f); win[r++] = k; } } if (ans < d[w ^ 1][t].v && d[w ^ 1][t].f) ans = d[w ^ 1][t].v; w ^= 1; } printf("%lld", ans); return 0; } ```