吃菜的区间版本。

我们用$tp_{l,r,k},dp_{l,r,k}$表示分别该神龙/xjc决策的时候，神龙还有$k$张抢吃券，未来的最大答案是多少。

那么，对于该神龙决策的时候：

神龙有两类决策： （1）吃左边的或者是吃右边的。 （2）不吃了，把主动权交给xjc。

xjc只有一种决策： （1）吃左边或者吃右边，然后把主动权交还给神龙。

做过前置题，此题就没什么细节的，具体看代码。 时间/空间复杂度$O(n^3)$，考虑到神龙的抢吃券最多积累到$255$张，或者是xjc的决策可以直接不用dp数组来保存，$1G$刚好够用。

#include<bits/stdc++.h>
#define maxn 505
#define ll long long
using namespace std;
ll dp[maxn][maxn][255],tp[maxn][maxn][255];
ll n,a[maxn];
ll DP(int l,int r,int k);
ll TP(int l,int r,int k);

int tot=0;
ll TP(int l,int r,int k)
{
	tot++;
	if (l>r) return 0;
	if (k>=(r-l+1)) return 0;
	ll tt=tp[l][r][k];
	if (tt!=0) return tt-1;
	ll ans=DP(l,r,k); //不选，继续把机会让给对方
	if (k>=1) 
	{
		ans=min(ans,TP(l+1,r,k-1));
		ans=min(ans,TP(l,r-1,k-1));
	}
	tp[l][r][k]=ans+1;
	return ans;	
}

ll DP(int l,int r,int k)
{
	tot++;
	if (l>r) {return 0;}
	ll tt=dp[l][r][k];
	if (tt!=0) return tt-1;
	ll ans=max(TP(l,r-1,k+1)+a[r],TP(l+1,r,k+1)+a[l]);
	dp[l][r][k]=ans+1;
	return ans;
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	DP(1,n,0);
	cout<<dp[1][n][0]-1<<endl;
}