1 //Accepted    300 KB    0 ms 2 //区间dp 3 //dp[i][j] 表示i到j第一个出场的最小diaosizhi 4 //对于i到j考虑元素i 5 //(1)i第一个出场，diaosizhi为 dp[i+1][j]+sum(i+1--j) 6 //(2)i不是第一个出场，而是第k个出场，则i+1到k+i-1这段区间第一个出场，k+i到j第k+1个出场 7 //diaoshizhi为dp[i+1][i+k-1] + a[i]*(k-1) + (dp[i+k][j]+k*sum(i+k--j)) 8 //sum为一段区间的diaosizhi的和，考虑k+i到j第k+1个出场相当于k+i到j第一个出场再加上k*(sum(i+k--j)) 9 #include <cstdio>10 #include <cstring>11 #include <iostream>12 using namespace std;13 const int imax_n = 105;14 int dp[imax_n][imax_n];15 int a[imax_n],sum[imax_n];16 int n;17 int min(int a,int b)18 {19     return a<b?a:b;20 }21 void Dp()22 {23     memset(dp,0,sizeof(dp));24     for (int l=2;l<=n;l++)25     {26         for (int i=1;i<=n;i++)27         {28             int j=i+l-1;29             if (j>n) break;30             dp[i][j]=dp[i+1][j]+sum[j]-sum[i];31             for (int k=1;k<=l;k++)32             {33                 dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+a[i]*(k-1)+dp[i+k][j]+k*(sum[j]-sum[i+k-1]));34             }35         }36     }37 }38 int main()39 {40     int T;41     scanf("%d",&T);42     for (int t=1;t<=T;t++)43     {44         scanf("%d",&n);45         sum[0]=0;46         for (int i=1;i<=n;i++)47         {48             scanf("%d",&a[i]);49             sum[i]=sum[i-1]+a[i];50         }51         Dp();52         printf("Case #%d: %d\n",t,dp[1][n]);53     }54     return 0;55 }

 1 //Accepted    4792 KB    281 ms 2 //区间dp 3 //dp[i][j][k] i到j整段区间在第k个出去时的最小花费 4 //考虑区间中的第一个元素i，有一下两种情况： 5 //（1）i在第k个出去，则i+1到j在第k+1个出去即dp[i+1][j][k+1] 6 //（2）i不在第k个出去，则i后必有一段在第k个出去，假设这段为i+1到m 7 //则有dp[i+1][m][k]+a[i]*(k+m-i)+dp[m+1][j][k+m-i+1] 8 #include <cstdio> 9 #include <cstring>10 #include <iostream>11 using namespace std;12 const int imax_n = 105;13 const int inf = 100000000;14 int dp[imax_n][imax_n][imax_n];15 int a[imax_n];16 int n;17 int min(int a,int b)18 {19     return a<b?a:b;20 }21 void Dp()22 {23     memset(dp,0,sizeof(dp));24     for (int i=1;i<=n;i++)25     {26         for (int k=1;k<=n;k++)27         {28             dp[i][i][k]=(k-1)*a[i];29         }30     }31     for (int i=1;i<n;i++)32     {33         for (int k=1;k<=n;k++)34         {35             dp[i][i+1][k]=min((k-1)*a[i]+k*a[i+1],k*a[i]+(k-1)*a[i+1]);36         }37     }38     for (int l=3;l<=n;l++)39     {40         for (int i=1;i<=n;i++)41         {42             int j=i+l-1;43             if (j>n) break;44             for (int k=1;k<=n;k++)45             {46                 dp[i][j][k]=inf;47                 dp[i][j][k]=min(dp[i][j][k],dp[i+1][j][k+1]+(k-1)*a[i]);48                 for (int m=i+1;m<=j;m++)49                 {50                     dp[i][j][k]=min(dp[i][j][k],dp[i+1][m][k]+a[i]*(k+m-i-1)+dp[m+1][j][k+1+m-i]);51                 }52             }53         }54     }55 }56 int main()57 {58     int T;59     scanf("%d",&T);60     for (int t=1;t<=T;t++)61     {62         scanf("%d",&n);63         for (int i=1;i<=n;i++)64         scanf("%d",&a[i]);65         Dp();66         printf("Case #%d: %d\n",t,dp[1][n][1]);67     }68     return 0;69 }