题目链接：这里

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

棋盘如图：

title

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

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

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

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

如果能赢输出“WIN!”

必败输出“LOSE!”

平局输出“Draw”

（都不输出引号）

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

title

对应： 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”

6
1 2 3 4 5 6
WIN!
5
4 5 6 7 8
LOSE!

//CDOJ 1402

#include <bits/stdc++.h>
using namespace std;
int dp[1<<20][2]; //dp[i][0]表示i这个状态柱爷的最大得分,dp[i][1]表示i这个状态卿学姐的最大得分
int viss[1<<20][2];
int vis[30];
int cal(int x){//计算状态x没构成三角形的虚线三角形的个数
    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[3*i+1]&&vis[3*i+2]&&vis[3*i+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(viss[now][flag]) return dp[now][flag];
    viss[now][flag] = 1;
    int last = cal(now);
    for(int i = 1; i <= 18; i++){
        if(((now>>i)&1)==0){
            int nxt = now|(1<<i);
            int num = last - cal(nxt);
            if(num > 0){//柱爷可以继续
                dp[now][flag] = max(dp[now][flag], dfs(nxt, flag)+num);
            }
            else{//换卿学姐
                dp[now][flag] = max(dp[now][flag], last - dfs(nxt, 1-flag));
            }
        }
    }
    return dp[now][flag];
}
int main(){
    int n, now = 0;
    scanf("%d", &n);
    while(n--){
        int x; scanf("%d", &x); now |= (1<<x);
    }
    int last = cal(now);
    int a = dfs(now, 0);
    int b = last - a;
    if(a > b) puts("WIN!");
    else if(a < b) puts("LOSE!");
    else puts("Draw");
    return 0;
}