[ZJOI2006]超级麻将（可行性dp）

题目描述

要判断某人是否胡牌，显然一个弱智的算法就行了，某中学信息学小组超级麻将迷想了想，决定将普通麻将改造成超级麻将。

所谓超级麻将没有了砣、索、万的区分，每种牌上的数字可以是1~100，而每种数字的牌各有100张。另外特别*的是，玩牌的人手里想拿多少张牌都可以，好刺激哦！

刺激归刺激，但是拿多了怎么胡牌呢？

超级麻将规定只要一个人手里拿的牌是若干句话（三个连续数字的牌各一张组成一句话，三张或者四张同样数字的牌也算一句话），再加上一对相同的牌，就算胡了。

作为信息学竞赛选手的你，麻烦你给这位超级麻将迷编个程序，判断能否胡牌。

Solution

可行性dp，设dp[i][j][k][0/1]为到第i个，当前用了k个，上一次用j个，出没出对子，能否可行。

转移：

出顺，则必须保证dp[i-1][a[i-2]-k][j-k][0/1]。

然后讨论一下出对，三个的，四个的，同层转移，

Code

#include<iostream>
#include<cstdio>
#include<bitset>
#include<cstring>
using namespace std;
bool dp[][][][];
int t,b[],a[];
int rd(){
    int x=;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c)){
        x=(x<<)+(x<<)+(c^);
        c=getchar();
    }
    return x;
}
int main(){
    t=rd();
    while(t--){
        memset(dp,,sizeof(dp));dp[][][][]=;
        for(int i=;i<=;++i){
          a[i]=rd();
          for(int j=;j<=a[i-];++j)
            for(int k=;k<=a[i];++k){
                if(k>)dp[i][j][k][]|=dp[i][j][k-][];
                if(k>)dp[i][j][k][]|=dp[i][j][k-][],dp[i][j][k][]|=dp[i][j][k-][];
                if(k>)dp[i][j][k][]|=dp[i][j][k-][],dp[i][j][k][]|=dp[i][j][k-][];
                if(j>=k&&a[i-]>=k)dp[i][j][k][]|=dp[i-][a[i-]-k][j-k][],dp[i][j][k][]|=dp[i-][a[i-]-k][j-k][];
            }
         }
         printf(dp[][a[]][a[]][]?"Yes\n":"No\n");
    }
    return ;
}