问题描述
题解
把拿走的过程反向,看做添加的过程,于是很显然的区间DP模型。
设(opt_{i,j})代表区间([i,j])中Bessie可以获得的最大值,显然有
[opt_{l,r}=sum_{l,r}-min(opt_{l+1,r},opt_{l,r+1})
]
于是爆了空间。
强行压成一维,滚动数组优化即可。
(mathrm{Code})
#include<bits/stdc++.h>
using namespace std;
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-'){
fh=-1;ch=getchar();
}
else fh=1;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
x*=fh;
}
const int maxn=5007;
int s[maxn],opt[maxn],n;
int main(){
read(n);
for(int i=1;i<=n;i++){
read(opt[i]);s[i]=s[i-1]+opt[i];
}
for(int len=2;len<=n;len++){
for(int l=1;l+len<=n+1;l++){
int r=l+len-1;
opt[l]=s[r]-s[l-1]-min(opt[l],opt[l+1]);
}
}
printf("%d
",opt[1]);
return 0;
}