题目链接：https://ac.nowcoder.com/acm/contest/21865/D

大意是给出n个城墙，每个城墙有一定数量的法阵，破坏他们可以获得经验值，同时消耗时间。每个城墙有一个固定的最大停留时间。且最多可以破坏m个城墙。当破坏掉一个城墙后，它邻近的城墙的经验值将增加被破坏城墙的经验值，求出最多能够获得多少经验值。

先01背包预处理每块城墙能够获得的最大经验值，这一步不难想到。

我们定义dp ij 为在第i块城墙开始，长度为j的区间范围内所能获取的最大经验值，它的值取决于从左向右走还是从右向左走。

code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[10010][35];
ll f[250];
ll a[10010];
int main()
{
	int n,m,t;
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
	{
		memset(f,0,sizeof f);
		int k;
		scanf("%d",&k);
		for(int j=1;j<=k;j++)
		{
			int jy,sj;
			cin>>jy>>sj;
			for(int ff=t;ff>=sj;ff--)
				f[ff] = max(f[ff],f[ff-sj]+jy);// 0 1 背包求解 
		}
		dp[i][1] = a[i] = f[t];//将每个城墙能够获得的最大经验值存放起来，并在区间dp的数组中存放初始值 
	}
	//dp[i][j] 表示选择在第i个城墙  直到i+j-1个城墙的范围内的最大值。   j为区间的长度。 
	for(int len=2;len<=m;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;//正下方这里最大值一定更新到了(i, m) 
			dp[l][len] = max(dp[l][len]  ,max(dp[l][len-1]*2+a[r]  ,dp[l+1][len-1]*2+a[l]));
			//我们只考虑当前，当前l到r取决于   (l,len-1)+最右边城墙   (l+1,len-1)+最左边城墙 
		}
	}
	ll res=0;
	for(int i=1;i<=n;i++){
		if(i+m-1>n) break;
			res = max(res,dp[i][m]);
	}
	cout<<res;
}