题解 P2593 【[ZJOI2006]超级麻将】

· · 题解

这道题我们考虑到单调将(就是单独的一对)有点麻烦

于是可以每局先枚举这一对是什么面值，在判断剩下牌是不是都是出(就是句话)

我们可以考虑面值

DPC[n][ll][l]表示现在面值为n的牌都出完了，且以前一位为开始的三连出了ll个

以这一位为开始的三连出了l个,是否可行

很明显边界是DP[0][0][0]=1，终点是DP[N][0][0]

但是状态有点多，考虑优化一下状态

考虑到同一开头的三连，超过2张其实没有意义，比如说出3个三连张相当于出三个大对(3张一样的牌)

以及4个三连相当于三个牌分别出一个大对，并且出一个三连

所以我们发现DP方程里的ll和l只需要是0,1,2就行了，而且没必要保证这个面值牌全出完，只要剩下牌数可以是3x+4y这样就行

所以我们就列出了状态数900，转移复杂度3的DP方程

再加上最开始枚举一对，复杂度是O(N*90000)

总之还是特别低的，用时36ms，是至今这道题最快最不占用内存的AC代码，比大部分前人代码快几十倍

#include <stdio.h>
#include <string.h>
bool DPC[110][3][3];
int N;
int CN[110];
bool Mod[110];
void Input()
{
    int wi;
    for(wi=1;wi<=100;++wi)
        scanf("%d",CN+wi);
    int ma,mb;
    for(ma=0;ma*3<=100;++ma)
        for(mb=0;mb*4+ma*3<=100;++mb)
            Mod[ma*3+mb*4]=1;
}
bool DPA()
{
    int win,wia,wib,wnn;
    memset(DPC,0,sizeof(DPC));
    DPC[0][0][0]=1;
    for(win=0;win<100;++win)
        for(wia=0;wia<3;++wia)
            for(wib=0;wib<3;++wib)
                if(DPC[win][wia][wib])
                    for(wnn=0;wnn<3&&wnn<=CN[win+1]-wia-wib;++wnn)
                        if(Mod[CN[win+1]-wia-wib-wnn])
                            DPC[win+1][wib][wnn]=1;
    return DPC[100][0][0];
}
void ACA()
{
    int wi;
    for(wi=1;wi<=100;++wi)
        if(CN[wi]>1)
        {
            CN[wi]-=2;
            if(DPA())
            {
                printf("Yes\n");
                return;
            }
            CN[wi]+=2;
        }
    printf("No\n");
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        Input();
        ACA();
    }
    return 0;
}
顺便吐槽一句...交题要养好手动选择语言的习惯...