1 /* 2 s[i]表示前i个的和 3 d[i][j]表示第i个到第j个直接花费的最小代价 4 5 d[i][j] = min(d[i][k] + d[k][j])(k from i to j) 6 7 */ 8 #include<cstdio> 9 #define inf 1<<30 10 int s[205],d[205][205]; 11 int main() 12 { 13 int n,i,j,k,x,t,temp; 14 while(~scanf("%d",&n)) 15 { 16 x = 0; 17 for(i=1; i<=n; ++i) 18 { 19 d[i-1][i] = x; 20 scanf("%d",&x); 21 d[i-1][i] += x; 22 s[i] = x + s[i-1]; 23 } 24 for(i=2; i<n; ++i)//控制区间元素个数为i+1个 25 { 26 for(j=i+1; j<=n; ++j)//区间的最后一个元素 27 { 28 t = inf; 29 for(k=j-i; k<j; ++k)//区间分割点处(j-i <= k < j) 30 { 31 temp = d[j-i][k] + d[k+1][j] + s[j] - s[j-i-1]; 32 if(temp < t)//找到[j-i,j]的最小价值。 33 t = temp; 34 } 35 d[j-i][j] = t; 36 } 37 } 38 printf("%d ",d[1][n]); 39 } 40 return 0; 41 } 42 43 //最优解，暂时没看懂。。。。 44 #include <cstdio> 45 const int N=210; 46 int n,t,stone[N],ans; 47 void combine(int k) 48 { 49 int tmp=stone[k]+stone[k-1]; 50 ans+=tmp; 51 for(int i=k; i<t-1; i++) 52 stone[i]=stone[i+1]; 53 t--; 54 int j; 55 for(j=k-1; j>0 && stone[j-1]<tmp; j--) 56 stone[j] = stone[j-1]; 57 stone[j] = tmp; 58 while(j >= 2 && stone[j] >= stone[j-2]) 59 { 60 int d = t - j; 61 combine(j-1); 62 j = t-d; 63 } 64 } 65 int main() 66 { 67 while(~scanf("%d",&n)) 68 { 69 for(int i=0; i<n; i++) scanf("%d",&stone[i]); 70 t=1,ans=0; 71 for(int i=1;i<n;i++) 72 { 73 stone[t++]=stone[i]; 74 while(t >=3 && stone[t-3]<=stone[t-1]) 75 combine(t-2); 76 } 77 while(t > 1) combine(t-1); 78 printf("%d " , ans); 79 } 80 return 0; 81 }