B 海盜分金币啦
Time Limit:1000MS Memory Limit:65535K
題型: 程式設計題 語言: 無限制
描述
現在有n個海盜，他們搶到了m個金币，現在他們準備分錢，但是由于他們聰明絕頂，
又不想直接平均配置設定，都想分到更多的錢，于是他們就想出了一種方法，就是讓他們
按順序排成一排，編号為1~n，現在由第一個人開始，每個人提出一種方案，如果這個
方案有除分錢的人以外一半或者一半以上的人同意，那麼他們就按照這個方案分錢，否
則的話，分錢的人就要被拖去喂鲨魚，繼續由下一個人分錢，直到有人提出一個滿意的方案。
現在你是第一個分錢的人，你需要保證自己存活的情況下令自己獲得的錢數盡可能的多。
PS：
1.生命>金錢
2.當其他海盜能獲得的金錢比分錢的海盜分給他的金錢多或者一樣時，他會反對你配置設定的方案。
輸入格式
第一行輸入一個T(1<=T<=10000)
接下來T行輸入n和m(1<=n<=1000,1<=m<=10000)
輸出格式
輸出你能得到的金錢數，當你死亡時，輸出-1，每個case一行。
輸入樣例
2
5 100
2 100
輸出樣例
97
-1
Hint
當5個人分100個金币的時候
假定五個人按照分錢順序寫為1~5号
從後向前推，如果1至3号強盜都喂了鲨魚，隻剩4号和5号的話，5号一定投反對票讓4号喂鲨魚，以獨
吞全部金币，四号必死。是以，4号惟有支援3号才能保命。
3号知道這一點，就會提出“100，0，0”的配置設定方案，對4号、5号一毛不拔而将全部金币歸為已有，
因為他知道4号即使一無所獲，但為了生命着想還是會投贊成票，他的方案即可通過。
不過，2号推知3号的方案，就會提出“98，0，1，1”的方案，即放棄3号，而給予4号和5号各一枚金
币。由于該方案對于4号和5号來說比在3号配置設定時更為有利，他們将支援他而不希望他出局而由3号來
配置設定。這樣，2号将拿走98枚金币。
同樣，2号的方案也會被1号所洞悉，1号并将提出（97，0，1，2，0）或（97，0，1，0，2）的方案，
即放棄2号，而給3号一枚金币，同時給4号（或5号）2枚金币。由于1号的這一方案對于3号和4号（或5号）
來說，相比2号配置設定時更優，他們将投1号的贊成票，1号的方案可獲通過，97枚金币可輕松落入囊中。這
無疑是1号能夠擷取最大收益的方案了！
答案是：1号強盜分給3号1枚金币，分給4号或5号強盜2枚，自己獨得97枚。配置設定方案可寫成
（97，0，1，2，0）或（97，0，1，0，2）。
當隻有2個人分100金币時：
推理同上：你不可能存在令最後一人滿意的方案
一道模拟題，wa了我很多次，原因是因為我沒想到如果某個海盜一定死了時，它會成為上一個海盜的“死黨”，是以上一個海盜可以省一個金币，甚至有可能活過來。開始的時候我但但是模拟了題目的資料，一直寫到13 100，果然太天真，100個金币你分很多個都分不完了，是以我就開始用金币為5來模拟，就發現了13 5 是0,14 5 是-1但是17 5是0,又奇迹地複活了，因為它有三個連續的死黨了。
是以，分析完後，根據DP的思路，從後開始計數。一路向上推，打個表（不然逾時），用個數組
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[1002][10002];
int find (int pos,int money)//找到有多少個連續的”死黨“
{
int i;
int i_count=0;
for (i=pos;i>=1;i--)
{
if (a[i][money]!=-1)
{
return i_count;
}
i_count++;
}
return i_count;
}
void init ()
{
int i,j;
int t;
for (j=1;j<=10000;j++)
{
a[1][j]=j;//拿到
a[3][j]=j;//get
}
for (j=1;j<=10000;j++)
{
a[2][j]=-1;//死忙
}
for (j=1;j<=10000;j++)
{
a[4][j]=j-2;//1---4要特殊處理，，自己看看"規律"吧
}
int need;
int money;
for (i=5;i<=1000;i++)
{
for (j=1;j<=10000;j++)
{
need=i/2;//需要賄賂的人數
if (a[i-1][j]==0)
{
money=need;//就需要這麼多個1
}
else if (a[i-1][j]==-1)//他會死的話..可以小很多個
{
t=find(i-1,j);
money=need-t;//還可以少t個
}
else
{
money=need+1;//4個海盜時是不符合這個規矩的
}
if (j<money)//不夠錢..死了
{
a[i][j]=-1;
}
else
{
a[i][j]=j-money;
}
}
}
return ;
}
void work ()
{
int n,m;
scanf ("%d%d",&n,&m);
printf ("%d\n",a[n][m]);
return ;
}
int main ()
{
init ();
int t;
scanf ("%d",&t);
while (t--)
{
work ();
}
return 0;
}