计算完每一关可获得的最大分数,就可以"用多重背包"来计算最终答案了。
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;
}
```