石子合并.c

算法分析ACM题目：石子合并算法 保证能运行！算法分析课程必备！

#include <stdio.h>
#include <string.h> 
#define  N     500 
#define  oo    200000
#define  MIN(a, b) (a)<(b)?(a):(b)
#define  MAX(a, b) (a)>(b)?(a):(b) 
 
typedef struct { int c, d; } Node;    
int n;
int v[N];                                              // ??????????????
int save[N];                                         // ???????????????????????????????? v ?????????????????????????????????????????????????????????????????? 
Node f[N][N];                                      // f[i][j]???????????????????????????? 
int sum[N][N];                                     // sum[i][j] ???????? i ??????????????j???????????? 


     
void Solve(int flag)                                // flag = 0??????????, flag = 1 ?????????? 
{
    int i, j, k, x, t, result;
    for(i = 1; i <= n; i++)                        // ????????????????????????????
        f[i][1].c = f[i][1].d = 0;  
    
    for(j = 2; j <= n; j++) {                     // ??????2????3??...n?????????????????????????? 
        for(i = 1; i <= n; i++) {
            t = sum[i][j];
            if(flag == 0) f[i][j].c = oo;          // ???????????????????????????? oo 
            else          f[i][j].c = 0;               // ???????????????????????????? 0 
            
            for(k = 1; k <= j-1; k++) {
                x = (i + k - 1)%n + 1;
                if((flag == 0 && f[i][k].c + f[x][j-k].c + t < f[i][j].c)
                ||(flag != 0 && f[i][k].c + f[x][j-k].c + t > f[i][j].c)) {
                    f[i][j].c = f[i][k].c + f[x][j-k].c + t;
                    f[i][j].d = k; 
                }
            }    
        }
    }
    
    result = f[1][n].c; k = 1;                  // ????????f[1][n], f[2][n]...f[n][n]???????????? 
    for(i = 2; i <= n; i++)
        if((flag == 0 && f[i][n].c < result) || (flag != 0 && f[i][n].c > result))
        {
            result = f[i][n].c;
            k = i;                                     // ?????? k 
        }
    
    printf("%d\n",result); 
             
}
     
main()
{
    int i, r, j, k, x, t; 
    scanf("%d", &n);       
        for(i = 1; i <= n; i++) scanf("%d", &v[i]);
        //memset(sum, 0, sizeof(sum)); 
        memcpy(save+1, v+1, n*sizeof(v[1])); 
        
        for(i = 1; i <= n; i++) sum[i][1] = v[i];
        for(j = 2; j <= n; j++)
        for(i = 1; i <= n; i++)
            sum[i][j] = v[i] + sum[i%n+1][j-1];
            
        Solve(0);
        memcpy(v+1, save+1, n*sizeof(v[1]));    // ???? v??????????????
        Solve(1); 
    
 
}