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
     
       9 #define inf 1<<3010 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
      
       < 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\n",d[1][n]);39     }40     return 0;41 }42 43 //最优解，暂时没看懂。。。。44 #include 
       
        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
        
         0 && stone[j-1]
         
          = 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
          
           =3 && stone[t-3]<=stone[t-1])75 combine(t-2);76 }77 while(t > 1) combine(t-1);78 printf("%d\n" , ans);79 }80 return 0;81 }