博弈dp.docx
《博弈dp.docx》由会员分享，可在线阅读，更多相关《博弈dp.docx（23页珍藏版）》请在冰点文库上搜索。
博弈dp
《博弈DP》
JiangnanUniversitLiyang
2014/10/24
题意：
有N个数，有一个区间[A,B],第一个人先取一个数，必须在区间内，后一次取必须比第一个数大，而且差值在区间内。
问最后两个人取的数的和的差值最大为多少。
constintmaxn=10008;
constintinf=1000000000;
intx[maxn];
inta,b,n;
intdp[maxn];
intdfs（intid）{
if（dp[id]!
=-inf）returndp[id];
intt=inf;
for（inti=id+1;i<=n;i++）{
if（x[i]-x[id]>=a&&x[i]-x[id]<=b）{
t=min（t,x[id]-dfs（i））;
}
}
if（t==inf）dp[id]=x[id];
elsedp[id]=t;
returndp[id];
}
intmain（）{
intt,i,ans;
cin>>t;
while（t--）{
cin>>n>>a>>b;
for（i=1;i<=n;i++）scanf（"%d",&x[i]）;
sort（x+1,x+1+n）;
for（i=1;i<=n;i++）dp[i]=-inf;
ans=-inf;
for（i=1;i<=n;i++）{
if（x[i]>=a&&x[i]<=b）ans=max（ans,dfs（i））;
}
if（ans==-inf）printf（"0\n"）;
elseprintf（"%d\n",ans）;
}
return0;
}
Alice和Bob玩一个游戏，有两个长度为N的正整数数字序列，每次他们两个 只能从其中一个序列，选择两端中的一个拿走。
他们都希望可以拿到尽量大的数字之和，并且他们都足够聪明，每次都选择最优策略。
Alice先选择，问最终Alice拿到的数字总和是多少？
constintmaxn=25;
constintinf=1000000000;
inta[maxn],b[maxn];
intsa[maxn],sb[maxn];
intdp[maxn][maxn][maxn][maxn];
intdfs（intl,intr,intL,intR）{
if（l>r&&L>R）return0;
if（dp[l][r][L][R]!
=-1）returndp[l][r][L][R];
dp[l][r][L][R]=0;
intsum=sa[r]-sa[l-1]+sb[R]-sb[L-1];
if（l<=r）{
dp[l][r][L][R]=max（sum-dfs（l+1,r,L,R）,dp[l][r][L][R]）;
dp[l][r][L][R]=max（sum-dfs（l,r-1,L,R）,dp[l][r][L][R]）;
}
if（L<=R）{
dp[l][r][L][R]=max（sum-dfs（l,r,L+1,R）,dp[l][r][L][R]）;
dp[l][r][L][R]=max（sum-dfs（l,r,L,R-1）,dp[l][r][L][R]）;
}
returndp[l][r][L][R];
}
intmain（）{
intt,i,n;
cin>>t;
while（t--）{
cin>>n;
sa[0]=0;
for（i=1;i<=n;i++）{
scanf（"%d",&a[i]）;
sa[i]=sa[i-1]+a[i];
}
sb[0]=0;
for（i=1;i<=n;i++）{
scanf（"%d",&b[i]）;
sb[i]=sb[i-1]+b[i];
}
memset（dp,-1,sizeof（dp））;
cout<}
return0;
}
两个公司从教育部轮流申请资金，如果库中钱充足的话那么就会拨给这个公司，如果一旦库中没有钱那么停止，如果申请的钱多余库中的那么教育部长会
把手中的m元钱给他之后申请结束，开始库中有n元钱，每个公司每次申请资金的范围是[1,k]，问先手的公司最多能得到多少钱，在得到最多钱的情况下
能让对手得到最少的钱数。
题解：
开始是博弈的想法，枚举每个人决策的平衡态，莫名其妙的过了，队友搞了dp，找到一组反例证明我的博弈想法是有错误的，dp应该是正解。
dp[i][0]代表的是当前剩余i元钱先手申请到的最多的钱，dp[i][1]代表剩余i元钱先手得到的最多钱时对手得到的最少的钱，
constintmaxn=22;
intn,m,k;
boolvis[10002][2];
typedefpairpt;
ptdp[10002][2];
ptdfs（intstate,intt）{
if（vis[state][t]）returndp[state][t];
vis[state][t]=1;
if（state==0）{
returndp[state][t]=pt（0,0）;
}
ptnow（0,0）;
for（inti=1;i<=k;i++）{
if（state>=i）{
ptnx=dfs（state-i,t^1）;
if（i+nx.second>now.first）{
now.first=i+nx.second;
now.second=nx.first;
}
elseif（i+nx.second==now.first）
now.second=min（now.second,nx.first）;
}
else{
if（now.firstnow.first=m;
now.second=0;
}
}
}
returndp[state][t]=now;
}
intmain（）{
inti;
while（cin>>n>>m>>k）{
memset（vis,0,sizeof（vis））;
ptt=dfs（n,0）;
printf（"%d%d\n",t.first,t.second）;
}
return0;
}
给定n个数字，A和B可以从这串数字的两端任意选数字，一次只能从一端选取（若干个）。
并且AB都尽力使自己选择的结果为最大的，可以理解成AB每一步走的都是最优的。
如果A先选择，则AB差值最大是多少。
constintmaxn=108;
constintinf=1000000000;
inta[maxn],sa[maxn];
intn;
intdp[maxn][maxn];
boolvis[maxn][maxn];
intsum（intl,intr）{
intt=0;
if（l<=r）returnsa[r]-sa[l-1];
}
intdfs（intl,intr）{
if（l>r）return0;
if（vis[l][r]）returndp[l][r];
ints=sum（l,r）;
intt=-inf;
for（inti=l;i<=r;i++）{
t=max（t,sum（l,i）-dfs（i+1,r））;
}
for（inti=r;i>=l;i--）{
t=max（t,sum（i,r）-dfs（l,i-1））;
}
vis[l][r]=1;
if（t==-inf）returndp[l][r]=0;
returndp[l][r]=t;
}
intmain（）{
inti;
while（cin>>n&&n）{
sa[0]=0;
for（i=1;i<=n;i++）{
scanf（"%d",&a[i]）;
sa[i]=sa[i-1]+a[i];
}
memset（vis,0,sizeof（vis））;
cout<}
return0;
}
题目大意：
有B个盒子里面放有G种颜色的宝石，两个人轮流选一个盒子将其中的宝石取出来放到一个锅里，然后其中没有S个相同颜色的宝石，它们就会聚合在一起变成一个魔法石（可能产生多个魔法石且锅里有可能有剩余的宝石），然后本轮的得分就是产生的魔法石的数量，且如果本轮某个人拿到了魔法石的话，那么下一轮他还可以继续选择盒子放入宝石，知道他在某一轮没有拿到魔法石，现在问两个人都采用最优策略的情况下，到最后先拿的那个人的得分与后拿的人的得分的差是多少。
constintmaxn=22;
intb,g,s;
vectorbg[maxn];
intscore[1<intsum[maxn];
boolvis[1<intdp[1<intdfs（intstate）{
if（vis[state]）returndp[state];
vis[state]=1;
for（inti=0;iif（state&（1<intt=score[state^（1<if（t>0）dp[state]=max（dp[state],dfs（state^（1<elsedp[state]=max（dp[state],score[0]-score[state]-dfs（state^（1<}
}
returndp[state];
}
intmain（）{
inti,n,x,j,k;
while（cin>>g>>b>>s）{
if（g==0&&b==0&&s==0）break;
for（i=0;ifor（i=0;iscanf（"%d",&n）;
while（n--）{
scanf（"%d",&x）;
bg[i].push_back（x）;
}
}
n=1<for（i=0;iscore[i]=0;
memset（sum,0,sizeof（sum））;
for（j=0;jif（（i&（1<for（k=0;k}
}
for（j=1;j<=g;j++）score[i]+=sum[j]/s;
}
memset（vis,0,sizeof（vis））;
memset（dp,0,sizeof（dp））;
cout<<2*dfs（n-1）-score[0]<}
return0;
}
题意：
20之内的数字，每次可以选一个数字，然后它的倍数，还有其他已选数的倍数组合的数都不能再选，谁先不能选数谁就输了，问赢的方法
constintN=1050005;
intt,n,w,start,dp[N],ans[25],an;
intgetnext（intstate,intx）{
for（inti=x;i<=20;i+=x）
if（state&（1<<（i-2）））
state^=（1<<（i-2））;
for（inti=2;i<=20;i++）{
if（state&（1<<（i-2）））{
for（intj=x;i-j>=2;j+=x）{
if（!
（state&（1<<（i-j-2））））{
state^=（1<<（i-2））;
break;
}
}
}
}
returnstate;
}
intdfs（intstate）{
if（dp[state]!
=-1）returndp[state];
if（state==0）returndp[state]=0;
for（inti=2;i<=20;i++）{
if（state&（1<<（i-2）））{
if（dfs（getnext（state,i））==0）
returndp[state]=1;
}
}
returndp[state]=0;
}
intmain（）{
intcas=0;
memset（dp,-1,sizeof（dp））;
scanf（"%d",&t）;
while（t--）{
start=0;an=0;
scanf（"%d",&n）;
for（inti=0;iscanf（"%d",&w）;
start|=（1<<（w-2））;
}
for（inti=2;i<=20;i++）{
if（start&（1<<（i-2）））{
if（dfs（getnext（start,i））==0）
ans[an++]=i;
}
}
printf（"Scenario#%d:
\n",++cas）;
if（an）{
printf（"Thewinningmovesare:
"）;
for（inti=0;iprintf（"%d",ans[i]）;
printf（".\n"）;
}
elseprintf（"Thereisnowinningmove.\n"）;
printf（"\n"）;
}
return0;
}
给你2n个人，两方各n个人，交叉坐，每个人可以取的石子有一个最大限制，总共有S颗石子，哪一方取了最后一颗石子就输了，问先取石子的这一方是否有必胜策略。
constintmaxn=1<<13+5;
boolvis[maxn][22];
intn;
inta[22];
intdp[maxn][22];
intdfs（intsum,intid）{
if（vis[sum][id]）returndp[sum][id];
vis[sum][id]=1;
if（sum==0）returndp[sum][id]=1;
for（inti=1;i<=a[id]&&i<=sum;i++）{
if（dfs（sum-i,（id+1）%（2*n））==0）returndp[sum][id]=1;
}
returndp[sum][id]=0;
}
intmain（）{
inti,s;
while（cin>>n&&n）{
cin>>s;
for（i=0;i<2*n;i++）scanf（"%d",&a[i]）;
memset（vis,0,sizeof（vis））;
cout<}
return0;
}
题目大意：
有一个数组，每次只能取第一个元素或者最后一个元素，两个人轮流取，问先手取能获得的最大值。
这是题很明显的博弈类型的DP，由于每次只能取首尾的元素，可以采用经典的枚举长度DP
DP[J][I][2] 第一维表示当前长度，第二维表示起点，第三维0表示先手最优值，1表示后手最优值。
由于两个人都是足够聪明，那么每次都会在当前状态取最优策略。
转移方程：
如果当前是先手取
dp[j][i][0]=max（dp[j-1][i+1][0]+a[i],dp[j-1][i][0]+a[i+j-1]）;//先手取，那么会选择最大值
dp[j][i][1]=min（dp[j-1][i+1][1],dp[j-1][i][1]）;//后手的只能取小的了，因为大的被先手取了
同理可得当前是后手取
dp[j][i][0]=min（dp[j-1][i+1][0],dp[j-1][i][0]）;
dp[j][i][1]=max（dp[j-1][i+1][1]+a[i],dp[j-1][i][1]+a[i+j-1]）;
因为状态是N*N*2=10^8，超出规定内存，改用滚动数组进行DP即可。
源代码：
constintmaxn=10001;
LLdp[2][maxn][2],a[maxn];
intmain（）{
inti,n,k;
while（cin>>n&&n）{
for（i=1;i<=n;i++）{
scanf（"%lld",&a[i]）;
dp[1][i][1]=a[i];
dp[1][i][0]=0;
}
k=0;
for（intlen=2;len<=n;len++）{
for（i=1;i+len-1<=n;i++）{
if（len%2==0）{
dp[k][i][0]=max（a[i]+dp[k^1][i+1][0],a[i+len-1]+dp[k^1][i][0]）;
dp[k][i][1]=min（dp[k^1][i][1],dp[k^1][i+1][1]）;
}
else{
dp[k][i][1]=max（a[i]+dp[k^1][i+1][1],a[i+len-1]+dp[k^1][i][1]）;
dp[k][i][0]=min（dp[k^1][i][0],dp[k^1][i+1][0]）;
}
}
k^=1;
}
cout<}
return0;
}
三堆石头，每次从一堆中取走若干，或者从两堆中取走相同的数量，最后取的人胜。
booldp[maxn][maxn][maxn];
voidDP（）{
memset（dp,0,sizeof（dp））;
inti,j,k,r;
for（i=0;i<=300;i++）{
for（j=0;j<=300;j++）{
for（k=0;k<=300;k++）{
if（dp[i][j][k]）continue;
for（r=1;i+r<=300;r++）dp[i+r][j][k]=1;
for（r=1;j+r<=300;r++）dp[i][j+r][k]=1;
for（r=1;k+r<=300;r++）dp[i][j][k+r]=1;
for（r=1;i+r<=300&&j+r<=300;r++）
dp[i+r][j+r][k]=1;
for（r=1;i+r<=300&&k+r<=300;r++）
dp[i+r][j][k+r]=1;
for（r=1;j+r<=300&&k+r<=300;r++）
dp[i][j+r][k+r]=1;
}
}
}
}
intmain（）{
DP（）;
inta,b,c;
while（cin>>a>>b>>c）cout<return0;
}
题意：
给定一个日期，两个人轮流走，每次可以走一月或者一天，问最后谁能走到2001.11.4这个日子
intmonthday[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
intleap（inty）{
return（（y%4==0）&&（y%100!
=0））||（y%400==0）;
}
structDay{
inty,m,d;
Day（）{}
Day（inty,intm,intd）{
this->y=y;
this->m=m;
this->d=d;
}
intvalid（）{//<=2001,11,4
if（y>2001）return0;
if（y<2001）return1;
if（m>11）return0;
if（m==11&&d>4）return0;
if（leap（y）&&m==
升级会员 