进阶实验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];elseans[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!