[TYVJ] P1055 沙子合并

 1 #include<stdio.h>
 2 
 3 int 
 4 min(int x,int y)
 5 {
 6     if (x<y) return(x);
 7     else return(y);
 8 }
 9 
10 int 
11 main(void)
12 {
13     int i,j,n,xi,x,y,minn,k,p;
14     int a[320][320],sum[320][320];
15     scanf("%d",&n);
16    for (i=1;i<=n;i++)
17     {
18          scanf("%d",&xi);
19          sum[1][i]=sum[1][i-1]+xi;
20          for(j=1;j<=i;j++)
21          sum[j][i]=sum[1][i]-sum[1][j-1];
22     }
23          
24     
25     for(i=1;i<=n-1;i++)
26         for(j=1;j<=n-i;j++)
27         { x=j;y=j+i;
28             minn=35111111;
29             for(k=x;k<=y-1;k++)
30             minn=min(minn,a[x][k]+a[k+1][y]+sum[x][k]+sum[k+1][y]);
31             a[x][y]=minn;
32         }
33     
34     printf("%d\n",a[1][n]);
35     return 0;
36 }
37     
38