[ZJOI2006]MAHJONG麻将

第一行一个整数N（N ≤ 100），表示玩了N次超级麻将。接下来N行，每行100个数a₁..a₁₀₀，描述每次玩牌手中各种牌的数量。a_i表示数字为i的牌有a_i张。（0 ≤ a_i ≤ 100）

3 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

C++11(clang++ 3.9) 解法, 执行用时: 21ms, 内存消耗: 3032K, 提交时间: 2019-03-09 13:11:26

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int N, a[110];
bool f[110][110][110][2];

int main(){
    scanf("%d", &N);
    while(N--){
        memset(f, 0, sizeof(f));
        for(int i=1; i<=100; i++)
            scanf("%d", &a[i]);
        f[0][0][0][0]=f[0][0][0][1]=true;
        for(int i=1; i<=100; i++)
            for(int j=0; j<=a[i-1]; j++){
                f[i][j][0][0]=f[i-1][a[i-2]][j][0];f[i][j][0][1]=f[i-1][a[i-2]][j][1];
                for(int k=0; k<=a[i]; k++){
                    if(k-3>=0)  f[i][j][k][0]|=f[i][j][k-3][0], f[i][j][k][1]|=f[i][j][k-3][1];
                    if(k-4>=0)  f[i][j][k][0]|=f[i][j][k-4][0], f[i][j][k][1]|=f[i][j][k-4][1];
                    if(j>=k&&i-2>=0&&a[i-2]>=k) f[i][j][k][0]|=f[i-1][a[i-2]-k][j-k][0], f[i][j][k][1]|=f[i-1][a[i-2]-k][j-k][1];
                    if(k-2>=0)  f[i][j][k][1]|=f[i][j][k-2][0];
                }
            }
        if(f[100][a[99]][a[100]][1]||f[100][a[99]][a[100]][0])  cout<<"Yes"<<endl;
        else    cout<<"No"<<endl;
    }
    return 0;
}

详情