jzoj3819 [NOI2015模拟9.9]取石子

Description

Alice和Bob兩個好♂朋友又開始玩取石子遊戲了。遊戲開始時，有N堆石子

排成一排，然後他們輪流操作（Alice先手），每次操作時從下面的規則中

任選一個：

1.從某堆石子中取走一個

2.合并任意兩堆石子

不能操作的人輸。Alice想知道，她是否能有必勝政策。

30% T<=10,N<=5,ai<=3

60% T<=100,N<=20,ai<=100

100% T<=4000,N<=50,ai<=1000

Solution

這種類規律題可以先從簡單情況想起。對于一堆的情況勝負由奇偶性決定，兩堆可以看成是一堆加上一個石子（合并操作）

繼續往下會出現問題，對于1顆石子的堆，在取走後隻減少了1步操作，即0顆石子的堆不能合并。那麼分别記錄1顆石子的堆數、剩下不為1的石子操作數的總和。n這麼小直接爆搜，擔心過不了就記憶化

操作分别有合并兩個1的堆、合并1和另一個不為1的堆、取走一個1、取走不為1的堆中的一個

Code

#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=;

int rec[][N];
int cnt,sum,n;

int dfs(int a,int b) {
    if (!a) return b&;
    if (b==) return dfs(a+,b-);
    if (rec[a][b]!=-) return rec[a][b];
    if (a&&!dfs(a-,b)) return rec[a][b]=;
    if (a&&b&&!dfs(a-,b+)) return rec[a][b]=;
    if (a>=&&!dfs(a-,b++(b!=))) return rec[a][b]=;
    if (b&&!dfs(a,b-)) return rec[a][b]=;
    return rec[a][b]=;
}

int main(void) {
    memset(rec,-,sizeof(rec));
    int T; scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        cnt=; sum=-;
        rep(i,,n) {
            int x; scanf("%d",&x);
            if (x==) cnt++;
            else sum+=x+;
        }
        if (sum==-) sum=;
        if (!dfs(cnt,sum)) puts("NO");
        else puts("YES");
    }
    return ;
}