UVa-10003

区间dp，O(n^3)的算法很容易想。先递增枚举区间的长度d，再枚举起点i，再枚举切点k(i<k<j)(j=i+d))。代码如下：(0.039s)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int maxn=55;
 6 int l,n;
 7 int p[maxn];
 8 int dp[maxn][maxn];
 9 int main()
10 {
11     while(scanf("%d",&l)&&l)
12     {
13         memset(dp,0x3f,sizeof(dp));
14         scanf("%d",&n);
15         for(int i=1;i<=n;i++) scanf("%d",&p[i]);
16         p[n+1]=l;
17         for(int d=1;d<=n+1;d++)
18             for(int i=0;i+d<=n+1;i++)
19             {
20                 if(d==1) dp[i][i+1]=0;
21                 else
22                 {
23                     for(int k=i+1;k<i+d;k++)
24                         dp[i][i+d]=min(dp[i][i+d],dp[i][k]+dp[k][i+d]);
25                     dp[i][i+d]+=p[i+d]-p[i];
26                 }
27             }
28         printf("The minimum cutting is %d.
",dp[0][n+1]);
29     }
30 }

然后看书上说可以用四边形不等式优化到O(n^2)，今天新买的黑书到手了，看了看讲解(p151,最优二分检索树)。大意是找k值的决策有单调性，利用此单调性并记录下来，可以在O(1)找到决策。代码如下：(0.029s) (rank 4!)

关于四边形不等式，http://blog.csdn.net/shiwei408/article/details/8791011 可以看这个博客。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int maxn=55;
 6 int l,n;
 7 int p[maxn];
 8 int dp[maxn][maxn];
 9 int kp[maxn][maxn];
10 int main()
11 {
12     while(scanf("%d",&l)&&l)
13     {
14         memset(dp,0x3f,sizeof(dp));
15         memset(kp,0,sizeof(kp));
16         scanf("%d",&n);
17         for(int i=1;i<=n;i++) scanf("%d",&p[i]);
18         p[n+1]=l;
19         for(int d=1;d<=n+1;d++)
20             for(int i=0;i+d<=n+1;i++)
21             {
22                 int j=i+d;
23                 if(d==1)
24                 {
25                     dp[i][i+1]=0;
26                     kp[i][i+1]=i+1;
27                 }
28                 else
29                 {
30                     for(int k=kp[i][j-1];k<=kp[i+1][j];k++)
31                         if(dp[i][k]+dp[k][j]<dp[i][j])
32                         {
33                             dp[i][j]=dp[i][k]+dp[k][j];
34                             kp[i][j]=k;
35                         }
36                     dp[i][j]+=p[j]-p[i];
37                 }
38             }
39         printf("The minimum cutting is %d.
",dp[0][n+1]);
40     }
41 }