[LUOGU] P2593 [ZJOI2006]超级麻将

f[a][b][c][i]表示考虑到第i个，第i位用了b个，第i-1位用了a个，此时有将/无将(c=1/0)的情况是否可达。

转移分以下几类：

1.调一个将 f[a][b][1][i]|=f[a][b-2][0][i];

2.碰 f[a][b][0/1][i]|=f[a][b-3][0/i][i];

3.杠 f[a][b][0/1][i]|=f[a][b-4][0/1][i];

4.顺 f[a][b][0/1][i]|=f[val[i-2]-b][a-b][0/1][i-1],其中b打完

注意到每个状态只与之前一行有关，可以滚动数组。

#include<iostream>

#include<cstring>

#include<cstdio>

#define CR ((i)&1)

#define PR (((i)-1)&1)

using namespace std;

inline int rd() {

    int ret=,f=;

    char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

const int MAXN=,N=;

int f[MAXN][MAXN][][];

int val[MAXN];

void init() {

    memset(f,,sizeof(f));

}

void solve() {

    init();

    f[][][][]=;

    for(int i=; i<=N; i++) val[i]=rd();

    for(int i=; i<=N; i++) {

        for(int a=; a<=val[i-]; a++) {

            for(int b=; b<=val[i]; b++) {

                f[a][b][][CR]=f[a][b][][CR]=;

                if(b>=) f[a][b][][CR]|=f[a][b-][][CR];

                if(b>=) f[a][b][][CR]|=f[a][b-][][CR],f[a][b][][CR]|=f[a][b-][][CR];

                if(b>=) f[a][b][][CR]|=f[a][b-][][CR],f[a][b][][CR]|=f[a][b-][][CR];

                if(b<=a&&b<=(i<?:val[i-]))

                f[a][b][][CR]|=f[val[i-]-b][a-b][][PR],

                f[a][b][][CR]|=f[val[i-]-b][a-b][][PR];

            }

        }

    }

    if(f[val[]][val[]][][]) puts("Yes");

    else puts("No");

}

int main() {

    int T;

    T=rd();

    while(T--) solve();

    return ;

}