三角形棋盘上的博弈游戏

题目连接：

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

Description

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

棋盘如图：

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

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

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

注：只算最小的三角形！（三个边围成的三角形）

如果能赢输出“WIN!”

必败输出“LOSE!”

平局输出“Draw”

（都不输出引号）

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

对应：

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;

}