[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 ;

}

巴特西

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

最新文章

热门文章