PKUSC2022 Mahjong
http://222.180.160.110:1024/contest/4813/problem/1
https://www.bilibili.com/video/BV1JB4y1R7AP/
这里是 PKUSC 当时的讲解视频。听说可以证明本题一定有 \(\le 5\) 的解。好神奇。
就比如说我们爆搜，\(9^4\times 13^4\) 这个显然干不动对吧，所以我们考虑反过来 DP。
我们先把字符串转化成计数数组，就是每种牌有多少片。不妨将 1m ~ 9s 编号为 \(1\sim 27\)，记 \(g_i\) 为编号为 \(i\) 的牌的数量。
为什么我们觉得 DP 不好打呢？因为换牌操作可以将两个毫不相干的牌的数量更改，不好记录状态。我们不妨直接将换牌拆成 丢弃一张牌 和 借取令一张牌 两个操作。很显然这两个操作数量是一样的，因为我们的牌数量自始至终不变。
对于比较简单的对子作为终局的情况，我们只关心对数是否为 \(7\)，所以设计状态：\(dp_{i,j}\) 表示前 \(i\) 张牌中凑出 \(j\) 个对子的最小代价。
那么就分 把当前牌丢一些 / 借一些拿去组对子 和 直接丢弃当前牌 两种方案。因为丢 / 借的数量是不确定的，直接 abs 一下就好。刷表，有：
最后我们的答案就来自 \(dp_{27,7}\)。然后注意这里我们的终局是 14 张牌 你能秒我，但起手只有 13 张牌，所以其实会有一个额外的借牌操作，假设答案为 \(x\)，那么其实 \(dp_{27,7}=2\times x+1\)。
有了对子的铺垫，面子手其实也还好。我们需要考虑的是对子和面子的个数。
但是有个问题，对子只用借 / 丢当前花色，但面子可能是会借 / 丢下一个 / 下下一个花色的。
所以干脆全部记录到状态里，令 \(f_{i,j,k,a,b}\) 表示当前在第 \(i\) 个花色，凑成了 \(j\) 个面子，\(k\) 个对子，需要 \(a\) 个 \(i+1\)，\(b\) 个 \(i+2\)。注意因为表示丢借有负数不太容易，不如就直接设成需要的数量了。
因为这个需要数量只是前面的花色对当前花色的需要 \(a\)，我们还要满足当前花色 自身 的需要 \(now\)（也就是说当前花色一共需要 \(a+now\) 张）。注意这里 \(a\) 张全部都是拿去借给前面的花色用的，自己不能用。
-
对于 \(k=0\) 且 \(now\ge 2\)，此时可以从 \(now\) 里拿两张出来凑对子，剩下的 \(now - 2\) 因为肯定 \(\le 2\)，所以只能全部拿去凑顺子。所以有：
\[f_{i+1,j+now-2,1,b+now-2, now-2}=f_{i,j,0,a,b}+|g_{i+1}-(a+now)| \] -
对于 \(now\ge 3\)，拿三张凑一面。有：
\[f_{i+1,j+now-2,k,b+now-3,now-3}=f_{i,j,0,a,b}+|g_{i+1}-(a+now)| \] -
对于 \(now\ne 0\)，可以凑顺子，有：
\[f_{i+1,j+now,k,b+now,now}=f_{i,j,0,a,b}+|g_{i+1}-(a+now)| \]注意不能跨花色借牌，也就是不能让 \(i=8/9/17/18/26/27\)。
答案就是 \(f_{27,4,1,0,0}\)。
然后这两个情况取一个 \(\min\) 就是答案。
namespace XSC062 {
using namespace fastIO;
using std::cin;
using std::getline;
using str = std::string;
int g[30];
int dp[30][15];
str sm, sp, ss;
int f[30][7][2][7][7];
int abs(int x) { return x >= 0 ? x : -x; }
int min(int x, int y) { return x < y ? x : y; }
void upd(int &x, int y) { x = min(x, y); return; }
int main() {
getline(cin, sm, 'm');
getline(cin, sp, 'p');
getline(cin, ss, 's');
for (auto i : sm) ++g[i - '0'];
for (auto i : sp) ++g[i - '0' + 9];
for (auto i : ss) ++g[i - '0' + 18];
// 打对子
memset(dp, 0x3f, sizeof (dp));
dp[0][0] = 0;
for (int i = 0; i < 27; ++i) {
for (int j = 0; j <= 7; ++j) {
if (dp[i][j] == 0x3f3f3f3f) continue;
upd(dp[i + 1][j], dp[i][j] + g[i + 1]);
upd(dp[i + 1][j + 1], dp[i][j] + abs(g[i + 1] - 2));
}
}
// 打飞机
memset(f, 0x3f, sizeof (f));
f[0][0][0][0][0] = 0;
for (int i = 0; i < 27; ++i)
for (int j = 0; j <= 4; ++j)
for (int k = 0; k <= 1; ++k)
for (int a = 0; a <= 4; ++a)
for (int b = 0; b <= 4; ++b) {
if (i % 9 == 8 && b) continue;
if (i % 9 == 0 && a + b) continue;
for (int now = 0; now <= 4; ++now) { // 对当前的额外需求
if (a + now > 4) continue;
int v = f[i][j][k][a][b] + abs(g[i + 1] - (a + now));
if (j + now <= 4 && b + now <= 4) // 直接硬配顺子
upd(f[i + 1][j + now][k][b + now][now], v);
if (now >= 2 && !k && j + now - 2 <= 4 && b + now - 2 <= 4) // 借两个去凑对子
upd(f[i + 1][j + now - 2][1][b + now - 2][now - 2], v);
if (now >= 3 && j + now - 2 <= 4 && b + now - 3 <= 4) // 借两个去凑三不带
upd(f[i + 1][j + now - 2][k][b + now - 3][now - 3], v);
}
}
// 拿来借走会算两次
print(min(dp[27][7], f[27][4][1][0][0]) / 2, '\n');
return 0;
}
} // namespace XSC062
标签：花色,int,选谈,240125,27,对子,now,杂题,dp From： https://www.cnblogs.com/XSC062/p/17988063