Codeforces 1110D Jongmah dp题意题解

93 阅读 0 评论 62 点赞

我是靠谱客的博主腼腆白开水，这篇文章主要介绍Codeforces 1110D Jongmah dp题意题解，现在分享给大家，希望可以做个参考。

文章目录

题意
题解

链接

题意

一种麻将的牌从 $1 \to m$ ,给你一手牌, $n$ 张,求这手牌最多能组成面子的数量.

题解

标准dp,所以写一下博客.
可以发现同样三个数字组成的顺子不会超过三组(可以当作三个刻子处理),因此可以定义 $d p [i] [j] [k]$ 表示前 $i$ 种牌, $i - 1, i, i + 1$ 组成的顺子数量为 $j$ , $i, i + 1, i + 2$ 组成的顺子数量为 $k$ 的最多面子数量.
转移的时候枚举 $l, j, k$ 分别表示最小数为 $i - 2, i - 1, i$ 的顺子数量.
此时转移方程为dp[i][j][k]=max(dp[i][j][k],dp[i-1][l][j]+k+(cnt[i]-j-k-l)/3);

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int yuzu=1e6;
typedef int fuko[yuzu|10];
fuko cnt,dp[3][3];
int main() {
  int i,n,m,j,k,l;
  read(n),read(m);
  for (i=1;i<=n;++i) ++cnt[read()];
  for (i=1;i<=m;++i) {
    for (j=0;j<3;++j) {
      for (k=0;k<3;++k) {
        for (l=0;l<3;++l) {
          if (cnt[i]>=j+k+l&&cnt[i+1]>=j+k&&cnt[i+2]>=k) 
            dp[j][k][i]=max(dp[j][k][i],dp[l][j][i-1]+k+(cnt[i]-j-k-l)/3); 
            // 借助i,i+1,i+2能够形成k个顺子,此时j+k+l个i已经被顺子用掉,剩下的i三个组成刻子
        }
      }
    }
  }
  printf("%dn",dp[0][0][m]);//由于cnt[m+1]肯定为0,不需要考虑m的顺子数.
}