BZOJ 1028 「JSOI2007」麻将

发表于 | 分类于 |

最近麻将题写上瘾了……（

显然地考虑枚举听的那张牌，然后判定是否可以和牌。
考虑 DP，设 \(f_{i,0/1,j,k}\) 表示考虑了前 \(i\) 种牌，无 / 有雀头，除去做面子的牌还有 \(j\) 组 \((i-1,i)\)，\(k\) 张 \(i\) 的情况下最多可以做多少面子。
则枚举第 \(i\) 种牌预留多少张，即可转移。
每次转移的时候考虑拿 \(2\) 张出来组雀头就行了。

最后因为刚好是 \(3m+2\) 张，所以肯定不会有多的 \((n-1,n)\) 或单独的 \(n\)，故只有 \(f_{n,1,0,0} = m\) 时才算和牌。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400;
const int M = 1e3;
int n,m,a[N + 5],flag;
int f[N + 5][2][3][3];
inline int dp()
{
    memset(f,-0x3f,sizeof f)，f[0][0][0][0] = 0;
    for(register int i = 1;i <= n;++i)
        for(register int j = 0;j < 3;++j)
            for(register int k = 0;k < 3;++k)
            {
                for(register int l = 0;l < 3 && j + k + l <= a[i];++l)
                    f[i][0][k][l] = max(f[i][0][k][l],f[i - 1][0][j][k] + j + (a[i] - j - k - l) / 3),
                    f[i][1][k][l] = max(f[i][1][k][l],f[i - 1][1][j][k] + j + (a[i] - j - k - l) / 3);
                if(a[i] >= 2)
                    for(register int l = 0;l < 3 && j + k + l <= a[i] - 2;++l)
                        f[i][1][k][l] = max(f[i][1][k][l],f[i - 1][0][j][k] + j + (a[i] - 2 - j - k - l) / 3);
            }
    return f[n][1][0][0] >= m;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x;
    for(register int i = 1;i <= 3 * m + 1;++i)
        scanf("%d",&x),++a[x];
    for(register int i = 1;i <= n;++i)
        ++a[i],dp() && (flag |= 1,printf("%d ",i)),--a[i];
    !flag && puts("NO");
}