文章目錄
- 題意
- 題解
鏈接
題意
一種麻將的牌從 1 → m 1 \to m 1→m,給你一手牌, n n n張,求這手牌最多能組成面子的數量.
題解
標準dp,所以寫一下博客.
可以發現同樣三個數字組成的順子不會超過三組(可以當作三個刻子處理),因此可以定義
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k]表示前
i
i
i種牌,
i
?
1
,
i
,
i
+
1
i-1,i,i+1
i?1,i,i+1組成的順子數量為
j
j
j,
i
,
i
+
1
,
i
+
2
i,i+1,i+2
i,i+1,i+2組成的順子數量為
k
k
k的最多面子數量.
轉移的時候列舉
l
,
j
,
k
l,j,k
l,j,k分別表示最小數為
i
?
2
,
i
?
1
,
i
i-2,i-1,i
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);
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("%d\n",dp[0][0][m]);//由于cnt[m+1]肯定為0,不需要考慮m的順子數.
}
Thank you.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/156355.html
標籤：AI
下一篇：C++筆試題