进阶实验2-3.1 海盗分赃 (25 point(s))

原题链接


讲道理，一眼看过去，我连题都读不懂……到底在讲什么啊？在问什么啊？sample 里的6怎么算出来的啊？……

然后想半天还是不懂……瞅瞅书才知道这是道博弈题。

下面给出我自己的accept代码。

#include<stdio.h>
#include<iostream>
using namespace std;
const int Max = 110;
int ans[Max] = { 0 };

int main() {
	int P = 0, D = 0;
	cin >> D >> P;
	int index = P - 2;
	while (index != 0) {
		int count = (P - index + 1) / 2;
		int max = 0;
		ans[index] = D;
		bool HashMap[Max] = { false };
		while (count != 0) {
			for (int i = index + 1; i <= P; i++) {
				if (ans[i] == max) {
					if (HashMap[i] == false) {
					ans[i]++;
					count--;
					HashMap[i] = true;
					}
				}
				if (count == 0)
					break;
			}
			max++;
		}
		for (int i = index + 1; i <= P; i++) {
			if (HashMap[i])
				ans[index] -= ans[i];
			else
				ans[i] = 0;
		}
		index--;
	}
	cout << ans[1];
	return 0;
}

基本思路

1. 首先就是
   
   递推的思路
   
   。想要知道一号海盗最高存活率且利益最高的方案，则必须
   
   预测二号海盗的分配方案
   
   ，在此之上拉拢半数海盗。而想要得知二号海盗的方案，则必须预测三号海盗的分配方案……依此类推。我们假设有n名海盗，那我们就必须
   
   从第（n-2）名海盗开始预测分配方案
   
   ，一直递推得到一号海盗的分配方案。（由于第（n-1）名海盗没得选，只能把钻石让给第n名海盗，所以我们从第（n-2）名开始预测）
2. 我们再仔细分析一下递推思路。数据采用题目样例。

• Dimond：10 ， Person：7
• 第六名海盗为了活命，只能把10个钻石全部交给7号。（
  
  最惨的一个位置
  
  ）
• 第五名为了不被喂鲨鱼，且能获得最多钻石，一个好的办法就是拉拢第六名海盗，分给第六名一个钻石，第七名莫得钻石。（
  
  如果第五名被喂鲨鱼，第六号会连一个钻石都得不到。
  
  ）
• 第四名为了不被喂鲨鱼，且能获得最多钻石，他需要拉拢两个人，这两个人自然是六号和七号，他应该要分给6号两个钻石，7号一个钻石，5号莫得钻石。（
  
  如果第四名被喂鲨鱼，那六号将只能获得1个钻石，7号将一个都没有。
  
  ）
• 第三名为了不被喂鲨鱼，且能获得最多钻石，他也需要拉拢两个人，这两个人自然是5号和7号。他应该要分给5号一个钻石，7号两个钻石。（
  
  如果第三名被喂鲨鱼，5号将一个钻石都没有，7号只能得一个钻石
  
  ）
• 接下来都是依此类推。
  
  

3. 接下来就是实现了。我的代码采用的是一维数组。
   • 先计算出第n-2名海盗需要拉拢的人数，记作
     
     count
     
     。
   • 从第n-2名海盗开始，设置==ans[n-2]为总的diamond数。从n-1开始历遍，当发现有位置为0时且没分配过，给其分配一个钻石，标记TA已经分配过。
   • 当历遍之后发现count依然不为0，继续历遍，发现有位置为1时且没被分配过，给其多分配一个钻石，以此类推。
   • 直到count为零，意味着该给的人都给了。
   • 再重新历遍，假如发现该位置没被分配过，分配0给TA，如果有被分配，则让ans[n-2]减去该位置分配的数字。
   • 接着预测下一位海盗的方案，依此类推。
   • 最后输出第一位海盗的方案。

心得

说实话没见过这种题，第一次见长见识了。其实具体实现还是蛮简单的只要明白了要怎么做，一直递推写循环就完事了。

Roman wasn’t built in a day.Just do it!