题意分析
就是在普通的石子合并的基础上，改成环形的而已。 转移方程依旧是
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j])
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
]
,
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
s
u
m
[
i
]
[
j
]
)
。
解决方法就是 将换拆成链，那么拆成连的过程总要将其长度变为2倍，DP依旧按照原来的DP方案，最主要的变化在于 答案的输出的时候。 原来线性合并的答案在
dp[1][n]
d
p
[
1
]
[
n
]
. 因为在不同地方拆开，所以，要在
dp[1][n],dp[2][n+1],dp[3][n]...dp[n−1][2∗n−1]
d
p
[
1
]
[
n
]
,
d
p
[
2
]
[
n
+
1
]
,
d
p
[
3
]
[
n
]
.
.
.
d
p
[
n
−
1
]
[
2
∗
n
−
1
]
中寻找最值，即为答案。
代码总览
#include<bits/stdc++.h>
using namespace std;
const int nmax =
255;
int sum[nmax];
int a[nmax];
int dp[nmax][nmax],dp2[nmax][nmax];
int n;
int main(){
while(
scanf(
"%d",&n)!=EOF){
for(
int i =
1;i<=n;++i)
scanf(
"%d",&a[i]);
for(
int i = n+
1;i<=
2*n;++i)
a[i] = a[i-n];
for(
int i =
1;i<=
2*n;++i) sum[i] = sum[i-
1] + a[i];
for(
int len =
2;len<=n;++len){
for(
int i =
1;i<=
2*n-len+
1;++i){
int j = i+len-
1;
dp[i][j] =
0;
dp2[i][j] =
0x3f3f3f3f;
for(
int k = i;k<j;++k){
dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+
1][j]+sum[j]-sum[i-
1]);
dp2[i][j] = min(dp2[i][j],dp2[i][k]+dp2[k+
1][j]+sum[j]-sum[i-
1]);
}
}
}
int ans1 =
0,ans2 =
0x3f3f3f3f;
for(
int i =
1;i<=n;++i){
ans1 = max(ans1,dp[i][n+i-
1]);
ans2 = min(ans2,dp2[i][n+i-
1]);
}
printf(
"%d\n",ans2);
printf(
"%d\n",ans1);
}
return 0;
}
