算法作业3-多米诺骨牌

每天属于自己的时间，就是慢慢的刷题的时候，啥也不用想，沉浸在写出最佳程序的过程中，沉浸在自己阅读大牛代码，提升自我的过程中，那种满足感，真的很让人享受<.>

题目:多米诺骨牌

现有 n 块 “多米诺骨牌” s1; s2; 。 。 。 ; sn 水平放成一排，每块骨牌 si 包含左右两 个部分，每个部分赋予一个非负整数值，如下图所示为包含 6 块骨牌的序列。骨牌可做 180 度旋转，使得原来在左边的值变到右边，而原来在右边的值移到左边，假设不论 si 如何
旋转，L[i] 总是存储 si 左边的值，R[i] 总是存储 si 右边的值，W [i] 用于存储 si 的状态： 当 L[i] <=R[i] 时记为 0，否则记为1，试采用分治法设计算法

解题思路：

方法：

在实验过程中，很容易观察到，在骨牌首尾补充两张牌00，00，就可以讲问题分成左右两个部分，就可以分别求出MAX0,MAX1,然后比较两者的值较大者就是题目要求的结果。

#include "stdafx.h"
#include <iostream>
using namespace std;

int max_duominuo(int* L, int* R, int start,int end,int* w) {//这里的start end是骨牌的序号
	/*思路
	很容易观察到，在骨牌收尾补充两张牌00，00，就可以讲问题分成左右两个部分，就可以分别求出MAX0,MAX1,然后比较两者的值
	较大者就是题目要求的结果。
	*/

	int mid = 0,maxL1,maxR1,MAX1, maxL0, maxR0, MAX0, tmp;
	if (end - start == 1)//此时证明只有两张牌，直接计算即可
	{
		return R[start] * L[end];
	}
	else
	{
		mid = (start + end) / 2;
		if (L[mid] > R[mid])
		{
			w[mid] = 1;
			maxL1=max_duominuo(L, R, start, mid, w);
			maxR1=max_duominuo(L, R, mid, end, w);
			MAX1 = maxL1 + maxR1;
			tmp = L[mid];
			L[mid] = R[mid];
			R[mid] = tmp;

			w[mid] = 0;
			maxL0 = max_duominuo(L, R, start, mid, w);
			maxR0 = max_duominuo(L, R, mid, end, w);
			MAX0 = maxL0 + maxR0;
			if (MAX1 > MAX0)
			{
				w[mid] = 1;
				return MAX1;
			}
			else
			{
				w[mid] = 0;
				return MAX0;
			}
		}
		else
		{
			w[mid] = 0;
			maxL0 = max_duominuo(L, R, start, mid, w);
			maxR0 = max_duominuo(L, R, mid, end, w);
			MAX0 = maxL0 + maxR0;
			tmp = L[mid];
			L[mid] = R[mid];
			R[mid] = tmp;

			w[mid] = 1;
			maxL1 = max_duominuo(L, R, start, mid, w);
			maxR1 = max_duominuo(L, R, mid, end, w);
			MAX1 = maxL1 + maxR1;
			if (MAX1 > MAX0)
			{
				w[mid] = 1;
				return MAX1;
			}
			else
			{
				w[mid] = 0;
				return MAX0;
			}
		}
	}
}

int main() {
	int n = 0,MAX=0;
	cout << "请输入骨牌个数n=";
	cin >> n;
	if (n <= 1) { cout << "骨牌过少，无法计算" << endl; return 0; }
	cout << endl;
	int *L = new int[n+2];
	int *R = new int[n+2];
	int *w = new int[n+2];

	for (int i = 1; i <= n; i++)
	{
		cout << "请输入骨牌S" << i << "的左骨牌数值: ";
		cin >> L[i];
		cout << "请输入骨牌S" << i << "的右骨牌数值: ";
		cin >> R[i];
		cout << endl;
		if (L[i] <= R[i])
		{
			w[i] = 0;
		}
		else
		{
			w[i] = 1;
		}
	}
	R[0] = 0;
	L[0] = 0;
	L[n + 1] = 0;
	R[n + 1] = 0;
	MAX = max_duominuo(L,R,0,n+1,w);
	cout << "最大值为：" << MAX<<endl;
	cout << "各个骨牌的状态为：";
	for (int i = 1; i <=n; i++)
	{
		cout << w[i] << " ";
	}
	return 0;
}