题解
$DP$。
时间复杂度为$O(n^2)$。
我的方法是设$f(i,j)$表示从$i$到$j$先手最高分数，然后
转移方程就是
但不知道为什么本机过了,洛谷上T了。
当然本题的官方做法更巧妙。
观察前面带有$\min$的式子，我们发现里面的$\min$可以拿掉，
因为我们刚好也算出了第二个人作为先手的最大解。
所以上面的$\min$就可以表示为$f$的形式，即
这样常数貌似很小，就可以过，还可以干掉一维空间。
修改前：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
int n,c[5005],dp[5005][5005]={0};
int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
void init(){
n=read();
for(int i=0;i<n;i++)c[i]=read();
}
void solve(){
int d1,d2,d3,b1,b2,lim;
for(int i=0;i<n;i++)
dp[i][i]=c[i];
for(int j=0;j<n-1;j++)
dp[j][j+1]=max(c[j],c[j+1]);
for(int j=2;j<n;j++){
d1=dp[0][j-2],d2=dp[1][j-1],d3=dp[2][j];
lim=n-j;
for(int i=0;i<lim;i++){
b1=d3;if(d2<d3)b1=d2;b1+=c[i];
b2=d1;if(d2<d1)b2=d2;b2+=c[i+j];
dp[i][i+j]=b1;if(b1<b2)dp[i][i+j]=b2;
d1=d2,d2=d3,d3=dp[i+3][i+1+j];
}
}
printf("%d\n",dp[0][n-1]);
}
int main(){
init();
solve();
return 0;
}
修改后：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
typedef long long ll;
int n,c[5005],dp[5005]={0},sum[5005]={0};
int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
void init(){
n=read();
for(int i=1;i<=n;i++)c[i]=read(),sum[i]=sum[i-1]+c[i];
}
void solve(){
for(int j=0;j<n;j++)
for(int i=1;i+j<=n;i++)
dp[i]=sum[i+j]-sum[i-1]-min(dp[i],dp[i+1]);
printf("%d\n",dp[1]);
}
int main(){
init();
solve();
return 0;
}