洛谷2593 [ZJOI2006]超级麻将—

题目：https://www.luogu.org/problemnew/show/P2593

发现三个连续牌的影响范围只有3、相同牌的影响范围只有1之后就可以dp了。

O(100^7)T飞。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int T,a[N];

bool dp[][N][N][N],flag;

int rdn()

{

    int ret=;char ch=getchar();

    while(ch>''||ch<'')ch=getchar();

    while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();

    return ret;

}

int main()

{

    T=rdn();

    while(T--)

    {

        for(int i=;i<=;i++)a[i]=rdn();

        for(int t=;t<=;t++)if(a[t]>=)

        {

            a[t]-=;

            memset(dp[],,sizeof dp[]);

            dp[][a[]][a[]][a[]]=;

            for(int i=;i<=;i++)

            {

                flag=;int d=(i&);

                memset(dp[!d],,sizeof dp[!d]);

                for(int x=;x<=a[i-];x++)

                    for(int y=;y<=a[i-];y++)

                        for(int z=;z<=a[i];z++)

                            if(dp[d][x][y][z])

                            {

                                int lm=min(x,min(y,z));

                                for(int k=;k<=lm;k++)

                                {

                                    dp[!d][y-k][z-k][a[i+]]|=(((x-k)%==)|((x-k)%==));

                                    if(dp[!d][y-k][z-k][a[i+]])flag=;

                                }

                            }

                if(!flag)break;

            }

            a[t]+=;

            if(flag)break;

        }

        if(flag)printf("Yes\n");else printf("No\n");

    }

    return ;

}

如果不枚举对子在哪而是带一个0/1在状态里的话可以少乘一个100。

如果不无脑记录前两个位置而是仅记录前一个位置、用三连的时候调用一下上一层的话可以少乘一个100。

　　这是因为最后要的只有dp[ ][0][0][0]，所以保存很多“之前位置还不是0”的状态比较浪费。

不枚举用了几个三连，而是每层用“从开头降到这里”更新一下本层，就能把”在本层用较少的三连“包括在“用单个位置从之前层降下来”。这样可以少乘一个100。

　　这里调了好久！必须是“从开头降到这里”，而不能是“从这里降到0”；因为从“这里”降的话需要判断本层是否可行，但这个可行是包括 i-2 的状态的，自己仅记录前一个位置的dp不能存下。如果是”从开头降到这里“的话，本层目前一定是可行的。

O(100^4)卡过。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int T,a[N];

bool dp[N][N][N][];

int rdn()

{

    int ret=;char ch=getchar();

    while(ch>''||ch<'')ch=getchar();

    while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();

    return ret;

}

int main()

{

    T=rdn();

    while(T--)

    {

        memset(dp,,sizeof dp);

        for(int i=;i<=;i++)a[i]=rdn();

        dp[][][a[]][]=;

        for(int i=;i<=;i++)

        {

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

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

                {

                    dp[i][x][y][]|=dp[i][x][y+][];

                    dp[i][x][y][]|=dp[i][x][y+][];

                    dp[i][x][y][]|=dp[i][x][y+][];

                    dp[i][x][y][]|=dp[i][x][y+][];

                    dp[i][x][y][]|=dp[i][x][y+][];

                    //在a[i]变成各种y之后尝试一下从开头降到这里(先降后单个弄)

                    dp[i][x][y][]|=dp[i-][a[i]-y][x+a[i]-y][];

                    dp[i][x][y][]|=dp[i-][a[i]-y][x+a[i]-y][];

                    //在a[i]变成各种y之后尝试一下取完

//                    dp[i][x][0][0]|=dp[i-1][y][x+y][0];//不能&dp[i][x+y][y],因含义是i-2==0

//                    dp[i][x][0][1]|=dp[i-1][y][x+y][1];//不&的话会出错：0 3 0(原为2)

                    //因为从当前降到0的话，需要判断当前是否可行

                    //可是降还需要i-2的也许有值，与表示“当前可行”的dp冲突，即无法表示当前是否可行

                    //而“从开头”降的话，一定可行 

                    //x之所以不是0，是因为这里用到dp[i-1][y][][]

                    if(!x)

                    {

                        dp[i+][y][a[i+]][]|=dp[i][][y][];

                        dp[i+][y][a[i+]][]|=dp[i][][y][];

                    }

//                    if(i<=3)

//                    {

//                        if(dp[i][x][y][0])printf("dp[%d][%d][%d][%d]=%d\n",i,x,y,0,dp[i][x][y][0]);

//                        if(dp[i][x][y][1])printf("dp[%d][%d][%d][%d]=%d\n",i,x,y,1,dp[i][x][y][1]);

//                    }

                }

        }

        puts(dp[][][][]?"Yes":"No");

    }

    return ;

}

巴特西

洛谷2593 [ZJOI2006]超级麻将——可行性dp

最新文章

热门文章