题意:有n个位置排成一排,从左到右第i个座位上摆放着分量为ai的菜肴。有个人坐在第s张椅子,每秒结束,她可以移动到相邻位置上也可以不动,她坐的位置上的菜肴都会被她吃了。计算她可以吃的最大总分量。他刚开始可以选择任意位置,她的时间最多为2n。
知识点:二维dp
分析:
g[s][t] 为在位置s移动不超过t次且不折返的吃掉菜肴的最大值。对于所有情况,只有两种,一种是一直走到头不折反,一种是折返走。向左移时,对于每一个座位 s
和时间 t
,由由子可以选择从左边的一个座位移动过来,即从 s-1
移动到 s
。因此,f[s][t]
可以通过比较 f[s-1][t-1]
(从左边移动过来时的最大份量)和 g[s][t]
(不移动方向时的最大份量)来更新。向右移动,由于我们需要先处理向左移动的情况,为了避免覆盖掉还未处理的值,我们选择从右向左更新数组。对于每一个座位 s
和时间 t
,由由子可以选择从右边的一个座位移动过来,即从 s+1
移动到 s
。因此,我们需要先更新 g[s][t]
,确保它包含了从右边移动过来时的最大份量,然后再更新 f[s][t]
。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+10;
ll sum[N],g[N][2*N],f[N][2*N];
int a[N],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int s=1;s<=n;s++){//不移动方向
for(int t=1;t<=2*n;t++){
int l=max(1,s-t);
int r=min(n,s+t);
g[s][t]=max(sum[s]-sum[l-1],sum[r]-sum[s-1]);
}
}
for(int s=1;s<=n;s++){//向左移动后折返
for(int t=1;t<=2*n;t++){
f[s][t]=max(f[s-1][t-1],g[s][t]);//向左移动和不动
}
}
for(int s=n;s>=1;s--){//向右移动然后折返
for(int t=1;t<=2*n;t++){
g[s][t]=max(g[s][t],g[s+1][t-1]);//向右移动和不动
f[s][t]=max(f[s][t],g[s][t]);
}
}
ll ans=0;
for(int i=1;i<=n;i++){
ll temp=0;
for(int j=1;j<=2*n;j++){
temp^=j*f[i][j];
}
ans^=(i+temp);
}
cout<<ans<<endl;
}