cpp1.cpp

石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆

#include <stdio.h>
#include <string.h> 
#define N 100 
#define oo 20000 
typedef struct { int c, d; } Node; 
int n;
int v[N]; 
int save[N]; 
Node f[N][N]; 
int sum[N][N]; 

void Print(int i, int j) 
{
int k, x;
if(j != 1) {
Print(i, f[i][j].d); 
x = (i + f[i][j].d - 1)%n + 1;
Print(x, j - f[i][j].d); 
for(k = 1; k <= n; k++) 
if(v[k] > 0)
{
if(i == k || x == k) printf("-%d ", v[k]); 
else printf("%d ", v[k]); 
}
printf("\n");
v[i] = v[i] + v[x]; 
v[x] = -v[x]; 
} 
}

void Solve(int flag) {
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++)
 {
for(i = 1; i <= n; i++) 
{
t = sum[i][j];
if(flag == 0) f[i][j].c = oo;
 else f[i][j].c = 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; 
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; 
}

printf("%s%d", flag == 0 ? "": "", result); 
printf("\n");
}

int main()
{
int i, j ; 
while(scanf("%d", &n), n) { 
for(i = 1; i <= n; i++) scanf("%d", &v[i]);
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])); Solve(1); 
}
return 0; 
}