9.22-动态规划 //石子合并//花生米

最新推荐文章于 2023-07-08 15:59:19 发布

铁锅炖鱼，铜锅涮肉

最新推荐文章于 2023-07-08 15:59:19 发布

阅读量416

点赞数 1

分类专栏： 2018秋学期-算法设计与分析

本文链接：https://blog.csdn.net/chengchencheng/article/details/83409911

版权

1.石子合并

描述：在一个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；比如有4堆石子：4 4 5 9 则最佳合并方案如下：
4 4 5 9 score: 0
8 5 9 score: 8
13 9 score: 8 + 13 = 21
22 score: 8 + 13 + 22 = 43

输入：可能有多组测试数据。当输入n=0时结束! 第一行为石子堆数n(1<=n<=100)；第二行为n堆的石子每堆的石子数,每两个数之间用一个空格分隔。

输出：合并的最小得分，每个结果一行。

输入样例：

4 4 4 5 9 0

输出样例：

43

#include<iostream>
#include<math.h>
#define MAX 100000
using namespace std;

int stone[100];
int n;
int l[100][100];

int search();
int num(int x, int y);

int main(){
	while(cin >> n && n){
		for(int i = 0; i < n; i++){
		    cin >> stone[i];
		}
		if(n == 1){
		    cout << '0' << endl;
		}
		else{
		    cout << search() << endl;
		}
	}
}

int search(){
	int i, j, k, len;
	int minnum = MAX;

	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			if(i == j){
			    l[i][j] = 0;
			}
			else{
			    l[i][j] = MAX;
			}
		}
	}

	for(len = 1; len < n; len++){
		for(i = 0, j = (i+len)%n; i < n; i++, j = (j+1)%n){
			for(k = 0; k < len; k++){
				l[i][j] = min(l[i][j], l[i][(i+k)%n] + l[(i+k+1)%n][j] + num(i, j));
				if(len == n-1){
				    minnum = min(minnum, l[i][j]);
				}
			}
		}
	}

	return minnum;
}

int num(int x, int y){
	int i, ans;
	ans = 0;

	if(x < y){
		for(