[ZJOI 2006]超级麻将

Description

Input

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

Output

输出N行，若胡了则输出Yes，否则输出No，注意区分Yes，No的大小写！

Sample Input

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

Yes
Yes
No

题解

这道题题解很多都是用贪心+$Hash$搜索做的，其实$DP$也可以解决这道题。

我们考虑选取麻将的先后是不互相影响的。且怎么选当前牌只会影响其相邻的几张牌，我们将这些影响的状态放入方程中，保证无后效性。

令： $f[i][j][k][0/1]$ 表示“择第 $i$ 号牌时，第 $i-1$ 号牌要打出 $j$ 张，第 $i$ 号牌要打出 $k$ 张，之前选的所有牌是否（ $0/1$ ）选择了将（对子）”是否可行。

于是就有转移方程：

考虑选这i号牌做将（对子）：
```
if (k>) f[i][j][k][]|=f[i][j][k-][];
```

考虑i号牌碰（三张相同）：

if (k>) f[i][j][k][]|=f[i][j][k-][],f[i][j][k][]|=f[i][j][k-][];

考虑i号牌杠（四张相同）：

if (k>) f[i][j][k][]|=f[i][j][k-][],f[i][j][k][]|=f[i][j][k-][];

考虑i-2,i-1,i三张牌吃（三个连续数字）：

if (j>=k&&a[i-]>=k) f[i][j][k][]|=f[i-][a[i-]-k][j-k][],f[i][j][k][]|=f[i-][a[i-]-k][j-k][];

最后结果为$f[100][a[99]][a[100]][1]$。

附的代码有个玄学的写法：当$i==1$时，$a[i-2]$越界？我也不知道它访问到哪去了，但$AC$了就苟活着吧。

人生处处是惊喜...难道不是吗？

 #include<set>

 #include<map>

 #include<ctime>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<cstdio>

 #include<string>

 #include<vector>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 #define RE register

 #define IL inline

 using namespace std;

 int n,a[];

 bool f[][][][];

 int main()

 {

     scanf("%d",&n);

     while (n--)

     {

         memset(f,,sizeof(f));

         for (RE int i=;i<=;i++) scanf("%d",&a[i]);

         f[][][][]=;

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

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

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

                 {

                     if (k>) f[i][j][k][]|=f[i][j][k-][];

                     if (k>) f[i][j][k][]|=f[i][j][k-][],f[i][j][k][]|=f[i][j][k-][];

                     if (k>) f[i][j][k][]|=f[i][j][k-][],f[i][j][k][]|=f[i][j][k-][];

                     if (j>=k&&a[i-]>=k) f[i][j][k][]|=f[i-][a[i-]-k][j-k][],f[i][j][k][]|=f[i-][a[i-]-k][j-k][];

                 }

         printf(f[][a[]][a[]][] ? "Yes\n":"No\n");

     }

     return ;

 }

秒客网