ZJOI2006 超级麻将

wjh15101051's space

卧薪尝胆，厚积薄发。

ZJOI2006 超级麻将

Date: Tue Sep 04 16:00:47 CST 2018

In Category: NoCategory

Description：

超级麻将每种牌都有 $100$ 张，判断能否胡牌。

$1\le n\le100$

Solution：

由于只能有连续的三个，所以设 $f[i][j][k][0/1]$ 表示到了第 $i$ 种牌，上一张牌有 $j$ 个，这张牌剩 $k$ 个，是否出了对子是否可行，每次只转移对应的，然后最后再倒序递推出相同的牌的情况。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 110

int a[MAXN];

bool f[2][MAXN][MAXN][2];

void work()

{

	memset(f,false,sizeof(f));

	int cur = 1;

    scanf("%d",&a[1]);

    f[cur][0][a[1]][0] = true;

    for(int i = a[1];i >= 0;--i)

	{

		if(f[cur][0][i + 3][0] || f[cur][0][i + 4][0])f[cur][0][i][0] = true;

		if(f[cur][0][i + 3][1] || f[cur][0][i + 4][1])f[cur][0][i][1] = true;

		if(f[cur][0][i + 2][0])f[cur][0][i][1] = true;

	}

    for(int k = 2;k <= 100;++k)

    {

    	cur = cur ^ 1;

    	memset(f[cur],false,sizeof(f[cur]));

        scanf("%d",&a[k]);

        for(int i = 0;i <= min(a[k - 2],a[k]);++i)

        {

            for(int j = i;j <= a[k - 1];++j)

            {

                if(f[cur ^ 1][i][j][0])f[cur][j - i][a[k] - i][0] = true;

                if(f[cur ^ 1][i][j][1])f[cur][j - i][a[k] - i][1] = true;

            }

        }

        for(int i = 0;i <= a[k - 1];++i)

        {

			for(int j = a[k];j >= 0;--j)

			{

				if(f[cur][i][j + 3][0] || f[cur][i][j + 4][0])f[cur][i][j][0] = true;

				if(f[cur][i][j + 3][1] || f[cur][i][j + 4][1])f[cur][i][j][1] = true;

				if(f[cur][i][j + 2][0])f[cur][i][j][1] = true;

			}

		}

    }

    if(f[cur][0][0][1])puts("Yes");

    else puts("No");

    return;

}

int main()

{

    int testcases = 0;

    scanf("%d",&testcases);

    while(testcases--)work();

    return 0;

}

In tag: DP-DP

wjh15101051