文档库

最新最全的文档下载
当前位置:文档库 > 石子合并 动态规划

石子合并 动态规划

有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动任意的2堆石子合并,合并花费为将的一堆石子的数量。设计一个算法,将这N堆石子合并成一堆的总花费最小(或最大)。

此类问题比较简单,就是哈夫曼编码的变形,用贪心算法即可求得最优解。即每次选两堆最少的,合并成新的一堆,直到只剩一堆为止。证明过程可以参考哈夫曼的证明过程。

#include

#include

#include

#include

using namespace std;

#define MAXN 100

int sum[MAXN];

int mins[MAXN][MAXN], maxs[MAXN][MAXN];

int n, stone[MAXN];

int sums(int i, int j)

{

if(i + j >= n)

{

return sums(i, n - i - 1) + sums(0, (i + j) % n);

}

else

{

return sum[i + j] - (i > 0 ? sum[i - 1] : 0);

}

}

void getBest(int& minnum, int& maxnum)

{

//初始化,没有合并,花费为0

for(int i = 0; i < n; ++i)

{

mins[i][0] = maxs[i][0] = 0;

}

//还需进行合并次数

for(int j = 1; j < n; ++j)

{

for(int i = 0; i < n; ++i)

{