CDOJ 1402 三角形棋盘上的博弈游戏 状压DP

三角形棋盘上的博弈游戏

题目连接:

http://mozhu.today/#/problem/show/1402

Description

柱爷有天上课无聊,于是和同桌卿学姐一起下一种奇特的棋:

棋盘如图:

CDOJ 1402 三角形棋盘上的博弈游戏 状压DP

在开始游戏前,棋盘上已经放好了一些边,然后柱爷先手,开始在棋盘上没有边的位置添加一条边上去

如果添加边后围成一个三角形则获得一分(对于棋盘上游戏开始前已经围好了的三角形,两个人都不得分)并且下一轮还该他!否则下一轮该另一个人。

如果两个人都以最优策略下棋,那么柱爷能赢么?

注:只算最小的三角形!(三个边围成的三角形)

如果能赢输出“WIN!”

必败输出“LOSE!”

平局输出“Draw”

(都不输出引号)

愚人王感觉这规则太抽象了,都没人赶预测柱爷能不能赢了,于是画了个图解释了下题意:

CDOJ 1402 三角形棋盘上的博弈游戏 状压DP

对应:

5

1 2 3 4 5

的情况,如果这是开局情况,那么此时两个人都是0分,改柱爷先下,

如果他在6的位置填一条边,那么4,5,6将围城一个小三角形,柱爷得一分。接下来还是改柱爷下棋。

如果他在18的位置填一条边,那么将无法构成三角形,柱爷不得分,接下来改卿学姐下棋。

一直这样,直到填完所有边后,游戏结束。此时分高的人获胜,分相同则平局。

Input

第一行一个正整数n,表示开始游戏前有多少条边已经被放上去了。

第二行有n个正整数,a1...an代表已经放好的边的编号。

1<=a1...an<=18

Output

一行,输出柱爷的结局。

如果能赢输出“WIN!”

必败输出“LOSE!”

平局输出“Draw”

Sample Input

6

1 2 3 4 5 6

Sample Output

WIN!

Hint

题意

题解:

直接暴力状压dp就好了

dp[i]表示i这个状态的时候,A能够拿到的最多数

注意trick,就是画线的时候,不仅仅可以占据一个三角形,有可能占据两个三角形哦

代码

#include<bits/stdc++.h>
using namespace std; int dp[1<<21][2];
int Dis[1<<21][2];
int cal(int x)
{
int vis[30];
memset(vis,0,sizeof(vis));
for(int i=1;i<=18;i++)
if((x>>i)&1)
vis[i]=1;
int ans = 0;
for(int i=0;i<6;i++)
if(vis[i*3+1]&&vis[i*3+2]&&vis[i*3+3])
ans++;
if(vis[3]&&vis[5]&&vis[7])ans++;
if(vis[6]&&vis[11]&&vis[13])ans++;
if(vis[9]&&vis[14]&&vis[16])ans++;
return 9-ans;
}
int dfs(int now,int flag)
{
if(Dis[now][flag])return dp[now][flag];
int last = cal(now);
Dis[now][flag]=1;
for(int i=1;i<=18;i++)
{
if(((now>>i)&1)==0)
{
int next = now|(1<<i);
int flag3 = cal(now)-cal(next);
if(flag3>0)
dp[now][flag]=max(dp[now][flag],dfs(next,flag)+flag3);
else
dp[now][flag]=max(dp[now][flag],last-dfs(next,1-flag));
}
}
return dp[now][flag];
} int main()
{
//freopen("1.in","r",stdin);
int n;
cin>>n;
int now = 0;
for(int i=0;i<n;i++)
{
int x;scanf("%d",&x);
now|=(1<<x);
}
int last = cal(now);
int a = dfs(now,0);
int b = last - a;
//cout<<last<<" "<<a<<" "<<b<<endl;
if(a>b)
cout<<"WIN!"<<endl;
else if(a==b)
cout<<"Draw"<<endl;
else if(a<b)
cout<<"LOSE!"<<endl;
}
上一篇:在Azure Container Service创建Kubernetes(k8s)群集运行ASP.NET Core跨平台应用程序


下一篇:登封小姐寿光小姐