P1880 [NOI1995]
石子合并
一道区间dp题目。
用 d[i][j] 表示从 i 到 j
的最大/最小得分，那么依次枚举长度 len，坐标 i
和 j，三层循环就可以 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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
int x=0,w=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')w=-1;
c=getchar();
}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
const int maxn=105*2;
int a[maxn],sum[maxn],d[maxn][maxn],d2[maxn][maxn];
int main()
{
int n=read();
for(int i=1;i<=n;i++)a[i]=a[i+n]=read();
for(int i=1;i<=(n+n);i++)sum[i]=sum[i-1]+a[i];
for(int len=2;len<=n;len++)
for(int i=1,j=i+len-1;i<n+n and j<n+n ;i++,j=i+len-1)
{
d[i][j]=INF;
for(int k=i;k<j;k++)
{
if(d[i][j]>d[i][k]+d[k+1][j]+sum[j]-sum[i-1])
d[i][j]=d[i][k]+d[k+1][j]+sum[j]-sum[i-1];
if(d2[i][j]<d2[i][k]+d2[k+1][j]+sum[j]-sum[i-1])
d2[i][j]=d2[i][k]+d2[k+1][j]+sum[j]-sum[i-1];
}
}
int ans1=INF,ans2=0;
for(int i=1;i<=n;i++)ans1=min(ans1,d[i][i+n-1]),ans2=max(ans2,d2[i][i+n-1]);
printf("%d\n%d\n",ans1,ans2);
return 0;
}
|
如果数据再大一点的话，需要用到平行四边形优化。
扩展：这道题的数据范围是 \(n\leq
100\) ,而我们给它还扩充到了 \(n\leq
200\)。那么如果n更大呢？比如 \(n\leq
40000\)？
这里有一道题目P5569
[SDOI2008] 石子合并
是的我们没法再用 40000*40000 的 DP 做了。
有兴趣可以去看题解。
