BZOJ1860【ZJOI2006】Mahjong麻将 < DP >

Posted on Symbols count in article: 940 Reading time ≈ 3 mins.

Problem

【ZJOI2006】Mahjong麻将

Time  Limit:  1  Sec\mathrm{Time\;Limit: \;1\;Sec}
Memory  Limit:  64  MB\mathrm{Memory\;Limit:\;64\;MB}

Description

很多人都知道玩麻将，当然也有人不知道，呵呵，不要紧，我在这里简要地介绍一下麻将规则：
普通麻将有砣、索、万三种类型的牌，每种牌有1∼91\sim 9个数字，其中相同的牌每个有四张，例如1砣∼9砣1砣\sim 9砣，1索∼9索1索\sim 9索，1万∼9万1万\sim 9万各44张，所以共36×3=10836\times 3=108张牌。胡牌时每人有1414张牌，其中只要某人手里有若干句话（就是同种类型的牌连续三张或同种牌三张），另外再加上一对，即可胡牌。当然如果全是对，叫七小对，也可以胡牌。
要判断某人是否胡牌，显然一个弱智的算法就行了，某中学信息学小组超级麻将迷想了想，决定将普通麻将改造成超级麻将。
所谓超级麻将没有了砣、索、万的区分，每种牌上的数字可以是1∼1001\sim 100而每种数字的牌各有100100张。另外特别自由的是，玩牌的人手里想拿多少张牌都可以，好刺激哦！
刺激归刺激，但是拿多了怎么胡牌呢？
超级麻将规定只要一个人手里拿的牌是若干句话（三个连续数字的牌各一张组成一句话，三张或四张同样数字的牌也算一句话），再加上一对相同的牌，就算胡了。
作为信息学竞赛选手的你，麻烦你给这位超级麻将迷编个程序，判断能否胡牌。

Input

第一行一个整数NN（N≤100N\le 100），表示玩了NN次超级麻将。 接下来NN行，每行100100个数a1,a2,⋯a100a_1,a_2,\cdots a_{100}，描述每次玩牌手中各种牌的数量。aia_i表示数字为ii的牌有aia_i张。（0≤ai≤1000\le a_i\le 100）

Output

输出NN行，若胡了则输出YesYes，否则输出NoNo，注意区分YesYes、NoNo的大小写！

Sample Input

1
2
3
4
3
2 4 0 0 0 0 0 …… 0（一共98个0）
2 4 2 0 0 0 0 …… 0（一共97个0）
2 3 2 0 0 0 0 …… 0（一共97个0）

Sample Output

1
2
3
Yes
Yes
No

标签：DP

Solution

一道比较常规的DP\mathrm{DP}。
记得另外一道省选麻将题可以贪心做，但此题不行，没有贪心策略。
考虑动态规划。发现一个数的牌数只可能影响它前后三个连续数的牌数（毕竟顺子只能三个连续），设f[i][j][k][0/1]f[i][j][k][0/1]表示把前ii中数字取完，取完之前数字为i−1i-1的共jj张，为ii的共kk张，0/10/1表示是否取了对子，能否有取法。那么根据不同情况，可以从取二对子、三对子、四对子、顺子的情况转移过来。
除了方程特判有点多，还是挺好写的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int a[105];    bool f[105][105][105][2];
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        memset(f, false, sizeof f), f[0][0][0][0] = true;
        for (int i = 1; i <= 100; i++)	scanf("%d", a+i);
        for (int i = 1; i <= 100; i++)
            for (int j = 0; j <= a[i-1]; j++)
                for (int k = 0; k <= a[i]; k++) {
                    if (k >= 2)	f[i][j][k][1] |= f[i][j][k-2][0];
                    if (k >= 3)	f[i][j][k][0] |= f[i][j][k-3][0];
                    if (k >= 3)	f[i][j][k][1] |= f[i][j][k-3][1];
                    if (k >= 4)	f[i][j][k][0] |= f[i][j][k-4][0];
                    if (k >= 4)	f[i][j][k][1] |= f[i][j][k-4][1];
                    if (j >= k && a[i-2] >= k)	f[i][j][k][0] |= f[i-1][(i >= 2 ? a[i-2] : 0)-k][j-k][0];
                    if (j >= k && a[i-2] >= k)	f[i][j][k][1] |= f[i-1][(i >= 2 ? a[i-2] : 0)-k][j-k][1];
                }
        printf("%s\n", f[100][a[99]][a[100]][1] ? "Yes" : "No");
    }
    return 0;
}