防御法阵

牛牛悄悄溜进了敌人的阵地，准备破坏敌人的城墙和防御法阵，破坏防御法阵可以给牛牛带来经验值。
敌人的城墙分为 $N$ 块，这些城墙排成一排，不成环。牛牛可以破坏 $M$ 块城墙，他可以从任意一点开始不断破坏两侧相邻的城墙。
每块城墙下方刻有诸多防御法阵。每个法阵需要耗费不同的时间来破坏。同时，为了防止对手发现，牛牛在每块城墙下仅能停留 $T$ 秒。经过的时间忽略不计。
破坏每个法阵会带来不同的经验值。并且，当相邻的城墙已经被破坏时，经验值会增加。
举例来讲，假设牛牛在某块城墙收获 $k$ 点经验值，但该城墙一侧（按照破坏顺序的规则，显然只有一侧可能被破坏）收获经验值为 $k_1$ ，
那么这块城墙的经验数变为 $k+k_1$ 。而当某块城墙一侧有n块城墙被破坏，其实际收获的经验值为 $k+k_1+k_2+...+k_n$
一段城墙得到的经验值为这一段城墙中每一段得到的经验值之和。
显然，最终的经验值还和破坏顺序有关。

现在，牛牛想知道他能得到的经验值最大是多少。

Note:上述的 $k_1,k_2,...,k_n$ 是指城墙左侧（或右侧）连续 $n$ 个城墙被破坏时获得的经验值。

大样例：https://uploadfiles.nowcoder.com/files/20211016/damage.zip

第一行三个整数 $N,M,T$ ，含义见题目描述。
接下来 $N$ 行，每行首先有正整数 $K$ 表示该块城墙下方的法阵数量，接下来 $2K$ 个正整数，依次是第 $1$ 个法阵破坏后的经验值 $v_i$ ，第 $1$ 法阵破坏的用时 $t_i$ 。
第 $2$ 个法阵破坏后的经验值和破坏用时，直到第 $K$ 个法阵。

#include <bits/stdc++.h> #define N 10005 #define LL long long using namespace std; int n, m, i, j, k, c, t, v, d[205], a[N]; LL ans, f[N][35]; int main(){ scanf("%d%d%d", &n, &m, &c); for(i=1; i<=n; i++){ memset(d, 0, sizeof(d)); scanf("%d", &k); while(k--){ scanf("%d%d", &v, &t); for(j=c; j>=t; j--){ d[j] = max(d[j], d[j-t]+v); } } f[i][1] = a[i] = d[c]; } for(c=2; c<=m; c++){ for(i=1; i+c-1<=n; i++){ f[i][c] = max(f[i][c-1]*2+a[i+c-1], f[i+1][c-1]*2+a[i]); } } for(i=1; i+m-1<=n; i++) ans = max(ans, f[i][m]); printf("%lld\n", ans); return 0; }

详情