**问题 B: 游戏(game)** **时间限制: 1 Sec 内存限制: 512 MB** **题目描述** 小R和小D在玩一个游戏。游戏涉及两个序列，序列 A 长度为 N，序列 B 长度为M。游戏共有 M 个回合，小R执先手，小R和小D轮流行动。 初始时游戏分数为 0。在第 i 个回合中，玩家需要选择序列 A 的一个长度为 $B_i$ 的区间，而且选择的区间应当严格被上一回合中选择的区间包含。假设上一回合中选择了区间$ [l, r]$，那么当前回合选择的区间$ [u, v] $应当满足$l

#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+5;
const ll inf=1e14+5;
int n,m,b[N],id[N];
ll a[N],q[N],dp[205][N];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=a[i-1];}for(int i=1;i<=m;i++)scanf("%d",&b[i]);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=-inf;for(int i=b[m];i<=n;i++)if(m&1)dp[m][i]=a[i]-a[i-b[m]];elsedp[m][i]=a[i-b[m]]-a[i]; for(int i=m-1;i>=1;i--){int L=1,R=0;id[0]=0;if(i&1)for(int j=i-1+b[i];j<=n-i+1;j++){int l=j-b[i]+b[i+1]+1,r=j-1;for(int k=id[R]+1;id[R]<r;k++)if(dp[i+1][k]!=-inf){while(R>=L&&q[R]>=dp[i+1][k])R--;q[++R]=dp[i+1][k];id[R]=k;}while(L<=R&&id[L]<l)L++;if(L<=R)dp[i][j]=q[L]+(a[j]-a[j-b[i]]);}elsefor(int j=i-1+b[i];j<=n-i+1;j++){int l=j-b[i]+b[i+1]+1,r=j-1;for(int k=id[R]+1;id[R]<r;k++)if(dp[i+1][k]!=-inf){while(R>=L&&q[R]<=dp[i+1][k])R--;q[++R]=dp[i+1][k];id[R]=k;}while(L<=R&&id[L]<l)L++;if(L<=R)dp[i][j]=q[L]-(a[j]-a[j-b[i]]);}}ll ans=-inf;for(int i=b[1];i<=n;i++)ans=max(ans,dp[1][i]);printf("%lld\n",ans);return 0;
}