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#include #include #define CR ((i)&1)#define PR (((i)-1)&1)using namespace std;inline int rd() { int ret=0,f=1; char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}const int MAXN=128,N=100;int f[MAXN][MAXN][2][2];int val[MAXN];void init() { memset(f,0,sizeof(f));}void solve() { init(); f[0][0][0][0]=1; for(int i=1; i<=N; i++) val[i]=rd(); for(int i=1; i<=N; i++) { for(int a=0; a<=val[i-1]; a++) { for(int b=0; b<=val[i]; b++) { f[a][b][0][CR]=f[a][b][1][CR]=0; if(b>=2) f[a][b][1][CR]|=f[a][b-2][0][CR]; if(b>=3) f[a][b][1][CR]|=f[a][b-3][1][CR],f[a][b][0][CR]|=f[a][b-3][0][CR]; if(b>=4) f[a][b][1][CR]|=f[a][b-4][1][CR],f[a][b][0][CR]|=f[a][b-4][0][CR]; if(b<=a&&b<=(i<2?0:val[i-2])) f[a][b][0][CR]|=f[val[i-2]-b][a-b][0][PR], f[a][b][1][CR]|=f[val[i-2]-b][a-b][1][PR]; } } } if(f[val[99]][val[100]][1][0]) puts("Yes"); else puts("No");}int main() { int T; T=rd(); while(T--) solve(); return 0;}