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");
}