洛谷 P1880。
本蒟蒻的第一道”普及+/提高”的 DP 题。
第一眼看上去一点思路都没有，后来靠上网找思路合理使用网络找到了思路：
dp数组 表示将第 堆石子合并到一起的分数，那么要求出 ，只要枚举每一个 ，求将 与 合并获得分数（即 ），在找出最大值。
得到代码像这样：
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
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <cstring>
using namespace std;
int dp[105][105];
int dp2[105][105];
int sum[105][105];
int dyna_p(int s,int e){
if(s==e)return dp[s][e]=0;
if(dp[s][e]>0)return dp[s][e];
int maxans=0;
for(int i=s;i<e;i++){
dyna_p(s,i);
dyna_p(i+1,e);
maxans=max(dp[s][i]+dp[i+1][e]+sum[s][i]+sum[i+1][e],maxans);
}
return dp[s][e]=maxans;
}
int dyna_p2(int s,int e){
if(s==e)return dp2[s][e]=0;
if(dp2[s][e]<0x3f3f3f3f)return dp2[s][e];
int maxans=0x3f3f3f3f;
for(int i=s;i<e;i++){
dyna_p2(s,i);
dyna_p2(i+1,e);
maxans=min(dp2[s][i]+dp2[i+1][e]+sum[s][i]+sum[i+1][e],maxans);
}
return dp2[s][e]=maxans;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>sum[i][i];
}
for(int i=0;i<n;i++){
int t=0;
for(int j=i;j<n;j++){
t+=sum[j][j];
sum[j][i]=sum[i][j]=t;
}
}
memset(dp2,0x3f,sizeof dp2);
cout<<dyna_p2(0,n-1)<<endl;
cout<<dyna_p(0,n-1)<<endl;
return 0;
}
|
然而并过不了。
原因在这里： 
居然是环形的！
解决方法也很简单，就是将所有可能都试一遍。比如 这几堆，就把 ，，， 都求一遍最大值就可以了。
AC Code
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <cstring>
using namespace std;
int dp[105][105];
int n;
int dp2[105][105];
int sum[105][105];
int dyna_p(int s,int e){
if(s==e)return dp[s][e]=0;
if(dp[s][e]>0)return dp[s][e];
int maxans=0;
for(int i=s;i!=e;i=(i+1)%n){
dyna_p(s,i);
dyna_p((i+1)%n,e);
maxans=max(dp[s][i]+dp[(i+1)%n][e]+sum[s][i]+sum[(i+1)%n][e],maxans);
}
return dp[s][e]=maxans;
}
int dyna_p2(int s,int e){
if(s==e)return dp2[s][e]=0;
if(dp2[s][e]<0x3f3f3f3f)return dp2[s][e];
int maxans=0x3f3f3f3f;
for(int i=s;i!=e;i=(i+1)%n){
dyna_p2(s,i);
dyna_p2((i+1)%n,e);
maxans=min(dp2[s][i]+dp2[(i+1)%n][e]+sum[s][i]+sum[(i+1)%n][e],maxans);
}
return dp2[s][e]=maxans;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>sum[i][i];
}
for(int i=0;i<n;i++){
int t=0;
int j=i;
do{
t+=sum[j][j];
sum[i][j]=t;
j=(j+1)%n;
}while(j!=i);
}
memset(dp2,0x3f,sizeof dp2);
int mina=0x3f3f3f3f;
for(int i=0;i<n;i++){
mina=min(mina,dyna_p2(i,(i+n-1)%n));
}
cout<<mina<<endl;
int maxa=0;
for(int i=0;i<n;i++){
maxa=max(maxa,dyna_p(i,(i+n-1)%n));
}
cout<<maxa<<endl;
return 0;
}
|
注：改代码一定要改全啊，i+1 改成 (i+1)%n 一定要全改完。要不然就会像我一样找错找半天。
2026.1.21 UPD：翻以前 Wordpress 备份翻到了这篇文章，改了点格式放上来了。