[bzoj1860 ZJOI2006] 超级麻将 (线性dp)

传送门

Description

Input

第一行一个整数N（N<=100），表示玩了N次超级麻将。 接下来N行，每行100个数a1..a100，描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。（0<=ai<=100）

Output

输出N行，若胡了则输出Yes，否则输出No，注意区分Yes，No的大小写！

Sample Input

3

2 4 0 0 0 0 0 …… 0（一共98个0）

2 4 2 0 0 0 0 …… 0（一共97个0）

2 3 2 0 0 0 0 …… 0（一共97个0）

Sample Output

Yes

Yes

No

Solution

yy:设dp[i][j][k][0/1] 表示前i个数 第i-1个数消去3和4=j 第i个数消去3和4=k 是否用过对子
能这样设计的原因是可以发现一个数若能对后面造成影响必然是消去3和4的那一部分起作用
然后。。。(扯不下去了qwq留坑)

Code

//By Menteur_Hxy
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;

inline int read() {
	int x=0,f=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x*f;
}

const int N=110;
bool jud[N],dp[N][3][3][2];
int T,da[N];

int main() {
	T=read();
	F(i,0,100) for(register int j=0;i*3+j*4<=100;j++) jud[i*3+j*4]=1;
	while(T--) {
		memset(dp,0,sizeof(dp));
		F(i,1,100) da[i]=read();
		dp[0][0][0][0]=1;
		F(i,0,100-1) F(j,0,2) F(k,0,2) {
			if(dp[i][j][k][0]) F(l,0,2) {
				int nxt=da[i+1]-j-k-l-2;
				if(nxt>=0&&jud[nxt]) dp[i+1][k][l][1]=1;
				nxt+=2;
				if(nxt>=0&&jud[nxt]) dp[i+1][k][l][0]=1;
			}
			if(dp[i][j][k][1]) F(l,0,2) {
				int nxt=da[i+1]-j-k-l;
				if(nxt>=0&&jud[nxt]) dp[i+1][k][l][1]=1;
			}
		}
		if(dp[100][0][0][1]) puts("Yes");
		else puts("No");
	}
}