方老师金币堆

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

虽然方老师赚到了很多钱，但是有些钱却非常难处理，经常会有人会以一大袋金币的方式来支付方老师的演讲报酬。现在方老师家里已经放置了

注意：开始时第

Input

输入有多组数据

每组数据第一行有

每组数据第二行

Output

输出

Sample input and output

Sample Input	Sample Output
4 1 1 1 1	8

思路：dp[i][r]=min(dp[i][r],dp[i][k-1]+dp[(i+k-1)%n+1][r-k])。其中，dp[i][r]表示第i堆到第i+r堆的最优解。

最朴素的算法：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cmath>
 7 using namespace std;
 8 
 9 const int N=205;
10 const int INF=0x7fffffff;
11 int n;
12 int a[N],sum[N],dp[N][N];
13 
14 int f();
15 
16 int main(){
17     //freopen("D:\input.in","r",stdin);
18     while(~scanf("%d",&n)){
19         sum[0]=0;
20         for(int i=1;i<=n;i++){
21             scanf("%d",&a[i]);
22             sum[i]=sum[i-1]+a[i];
23         }
24         printf("%d
",f());
25     }
26     return 0;
27 }
28 int f(){
29     for(int i=1;i<=n;i++)   dp[i][0]=0;
30     for(int r=1;r<n;r++){
31         for(int i=1;i<=n;i++){
32             int j=i+r;
33             dp[i][r]=INF;
34             for(int k=1;k<=r;k++){
35                 if(i+k>n)   dp[i][r]=min(dp[i][r],dp[i][k-1]+dp[(i+k)%n][r-k]);
36                 else    dp[i][r]=min(dp[i][r],dp[i][k-1]+dp[i+k][r-k]);
37             }
38             if(i+r>n) dp[i][r]+=sum[(i+r)%n]+sum[n]-sum[i-1];
39             else    dp[i][r]+=sum[i+r]-sum[i-1];
40         }
41     }
42     int ans=INF;
43     for(int i=1;i<=n;i++) ans=min(ans,dp[i][n-1]);
44     return ans;
45 }

5ms

四边形不等式优化：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cmath>
 7 using namespace std;
 8 
 9 const int N=205;
10 const int INF=0x7fffffff;
11 int n;
12 int a[N],sum[N],dp[N][N],s[N][N];
13 
14 int f();
15 
16 int main(){
17     //freopen("D:\input.in","r",stdin);
18     while(~scanf("%d",&n)){
19         sum[0]=0;
20         for(int i=1;i<=n;i++){
21             scanf("%d",&a[i]);
22             sum[i]=sum[i-1]+a[i];
23         }
24         printf("%d
",f());
25     }
26     return 0;
27 }
28 int f(){
29     for(int i=1;i<=n;i++)   dp[i][0]=0,s[i][0]=1;
30     for(int r=1;r<n;r++){
31         for(int i=1;i<=n;i++){
32             int j=i+r;
33             dp[i][r]=INF;
34             for(int k=s[i][r-1];k<=s[i+1][r-1]+1;k++){
35                 int t=dp[i][k-1]+dp[(i+k-1)%n+1][r-k];
36                 if(dp[i][r]>t){
37                     dp[i][r]=t;
38                     s[i][r]=k;
39                 }
40             }
41             if(i+r>n) dp[i][r]+=sum[(i+r)%n]+sum[n]-sum[i-1];
42             else    dp[i][r]+=sum[i+r]-sum[i-1];
43         }
44     }
45     int ans=INF;
46     for(int i=1;i<=n;i++) ans=min(ans,dp[i][n-1]);
47     return ans;
48 }

0ms

关于四边形不等式优化，详见：http://www.cnblogs.com/jiu0821/p/4493497.html