Codeforces Gym 100015F Fighting for Triangles 状态压缩DP

　　　　　　　F Fighting for Triangles　　　　　

Description

Andy and Ralph are playing a two-player game on a triangular board that looks like the following:

1 2
3
4 5 7 8
6 9
10 11 13 14 16 17
12 15 18

At each turn, a player must choose two adjacent vertices and draw a line segment that connects them.
If the newly drawn edge results in a triangle on the board (only the smallest ones count), then the player
claims the triangle and draws another edge. Otherwise, the turn ends and the other player plays. The
objective of the game is to claim as many triangles as possible. For example, assume that it is Andy’s turn,
where the board has ﬁves edges as shown in the picture below. If Andy draws edge 6, then he will claim the
triangle formed by edge 4, 5, and 6, and continue playing.

Given a board that already has some edges drawn on it, decide the winner of the game assuming that
both Andy and Ralph play optimally. Andy always goes ﬁrst. Note that if a triangle exists on the board
before the ﬁrst move, neither player claims it.

Input

The input consists of multiple test cases. Each test case begins with a line containing an integer N,5 !
N ! 10, which indicates the number of edges that are already present on the board before the game begins.
The next line contains N integers, indicating the indices of these edges. The input terminates with a line
with N = 0. For example:

Output

For each test case, print out a single line that contains the result of the game. If Andy wins, then print out
“Andy wins”. If Ralph wins, then print out “Ralph wins”. If both players get the same number of triangles,
then print out “Draw”. Quotation marks are used for clarity and should not be printed. For example, the
correct output for the sample input above would be:

Sample Input

1 2 3 4 5 6

4 5 6 7 8

Sample Output

Andy wins

Ralph wins

题意：给一个图，是一个正三角形，在三角形内部（包括边缘）有18个点，每次你可以去相邻的点画一条线段，假如这条线段可以和相邻的点构成一个新的三角形，那么价值+1

　　　　现在有两个人玩这个比赛，A先手，假如A不能获取价值才轮到B 知道所有可能的线段全部画完，问你A,B谁获取的价值更大

　　开始给你n个点，表示这n个点间有线段已经被画完

题解：电数n<=18我们设定 x为当前被画掉的状态，且f先手

那么记忆花搜索dp[x][f] 表示就是当前x情况下 f先手 a 取得的价值是多少

　　爆搜记忆就好

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long ll;
const int N = 1<<21;
int dp[N][2],v[21];
int cal(int x) {
    memset(v,0,sizeof(v));
    int ret = 0;
    for(int i = 17; i >= 0; i--) if(x & (1<<i)) v[i + 1] = 1;
    for(int i = 1; i <= 16; i += 3) {
        if(v[i] && v[i+1] && v[i+2]) ret++;
    }
    if(v[3] && v[5] && v[7]) ret++;
    if(v[6] && v[11] && v[13]) ret++;
    if(v[9] && v[14] && v[16]) ret++;
    return ret;
}
int dfs(int n,int f) {
    if(dp[n][f] != -1) return dp[n][f];
    int last = 9 - cal(n);
    dp[n][f] = 0;
    for(int i = 0; i < 18; i++) {
        if(((1<<i) & n) != 0) continue;
        int nex = n|(1<<i);
        int g = cal(nex) - cal(n);
        if(g) dp[n][f] = max(dp[n][f],dfs(nex,f) + g);
        else dp[n][f] = max(dp[n][f], last - dfs(nex,1-f));//
    }
    return dp[n][f];
}
int main() {
    int n, x;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d",&n)!=EOF) {
        if(n == 0) break;
        int f = 0;
        for(int i = 1; i <= n; i++) scanf("%d",&x), f |= (1<<(x-1));
        int last = 9 - cal(f);
       // for(int i = 1; i <= 18; i++)if(v[i]) printf("1");else cout<<0;
        int a = dfs(f,0);
        int b = last - a;
        if(a > b) printf("Andy wins
");
        else if(a == b) printf("Draw
");
        else printf("Ralph wins
");
    }
    return 0;
}

代码