自动搬运

查看原文

来自洛谷，原作者为

	do_while_true 水

搬运于2025-08-24 22:09:16，当前版本为作者最后更新于2021-07-09 21:12:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

获得可能更优的阅读体验

快跑。

本篇文章重点在于整理如何优美地写完这道题。

先手写张攻略理解下规则。

发现 $>15$ 张的「和牌」方式不需考虑，没有 「$[3\times 4+2]$」 的更优。若是宝牌： $\binom{4}{4}\times 2<\binom{4}{3}\times2$；若不是宝牌：$\binom{4}{4}<\binom{4}{3}$，所以 $>15$ 张的「和牌」方式中的杠子可以换成刻子，答案更优。

「宝牌」数对「达成分数」的贡献可以拆开分给每个数。

现在「和牌」方式仅剩 「$[3\times 4+2]$」、「七对子」、「国士无双」 三种方案。前两种分别 dp 一下，后者暴力算答案。

• 预处理

为了方便做，先给每种牌一个标号。因人而异，建议万索筒这三个序数牌放在一起编号，因为他们各自可以组成顺子。

bool baopai[35];
int cnt[35]; 

//为了方便，我把和计算答案有关的，和输入有关的分别放到namespace中。
 
namespace Calc {
	int fac[15], pow2[50];
	void Cpre() { fac[0] = 1; for(int i = 1; i <= 10; ++i) fac[i] = fac[i-1] * i; pow2[0] = 1; for(int i = 1; i <= 30; ++i) pow2[i] = pow2[i-1]*2; }
	inline ll C(int x, int y) { return fac[x] / fac[y] / fac[x-y]; }
	inline ll cbp(int x, int y) { return baopai[x] ? pow2[y] : 1; }
}
using namespace Calc;
namespace How_to_get {
	//1  -> 9   1m,2m,3m...
	//10 -> 18  1p,2p,3p...
	//19 -> 27  1s,2s,3s...
	//28:E  29:S  30:W  31:N  32:Z  33:B  34:F
	inline char getcha() { char ch; std::cin >> ch; return ch; }          
	inline int getpai() {
		char ch = getcha(); if(ch == '0') return 0;
		if(ch >= '1' && ch <= '9') {
			char ch2 = getcha();
			if(ch2 == 'm') return ch-'0';
			if(ch2 == 'p') return 9+(ch-'0');
			if(ch2 == 's') return 18+(ch-'0');
		}
		switch(ch) {
			case 'E': return 28;
			case 'S': return 29;
			case 'W': return 30; 
			case 'N': return 31; 
			case 'Z': return 32; 
			case 'B': return 33; 
			case 'F': return 34; 
		}
		return 0;
	}
	void read1() {
		int x = getpai();
		while(x) {
			cnt[x]--;
			x = getpai();
		}
	}
	void read2() {
		int x = getpai();
		while(x) {
			baopai[x] = 1;
			x = getpai();
		}
	}
}
using namespace How_to_get;

• 「国士无双」

直接暴力做。列出可以「国士无双」的牌的编号，先假装全只选一个算出答案，然后枚举哪张牌选了两遍，算一下答案即可。

int gsws[15] = {0, 1, 9, 10, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34};
ll Gsws() {
	Cpre();
	ll sumq = 0, mul = 1, bps = 0;
	for(int i = 1; i <= 13; ++i) if(cnt[gsws[i]] == 0) return 0;
	for(int i = 1; i <= 13; ++i) mul *= cnt[gsws[i]], bps += baopai[gsws[i]];
	for(int i = 1; i <= 13; ++i) {
		if(cnt[gsws[i]] <= 1) continue ;
		sumq = Max(sumq, mul / cnt[gsws[i]] * C(cnt[gsws[i]], 2) * pow2[bps+baopai[gsws[i]]]);
	}
	return sumq * 13;
}

• 「$[3\times 4+2]$」

算是最难写的一部分。

设 $f_{i,j,k,c1,c2}$ 为考虑前 $i$ 种牌，$j$ 个面子，有 $k$ 个雀头，第 $i$ 种牌选了 $c_1$ 个，第 $(i-1)$ 种牌选了 $c_2$ 个的最高分数。

填表法是前面状态转移到当前状态，涉及减法有点绕。考虑刷表法，从当前状态转移到后面状态。值得注意的是选取 $c_1,c_2$ 意义为选了几个而不是剩下几个也是避免 dp 的时候关于状态的下标涉及减法，不太好绕得过来。

有两种 dp 方式，一种是 $(i+1)$ 能作为结尾顺顺子的，一种是不能的。（因为选择刷表法，所以枚举 $i$ 之后看的牌是 $(i+1)$ 号牌。）

注意到不仅有八筒不能往下顺下去，八万和八索也不能往下顺下去，不能出现八万九万一索顺子的情况。

对于前一种，有以下几种转移方法：

• 一组刻子；

• 一组或两组顺子；

• 一组刻子，一组顺子；

• 一组雀头；

• 一组雀头，一组顺子；

• 一组雀头，两组顺子；

• 什么也不选。

因为三个顺子可以转化成三个刻子，所以不需要三个顺子的转移，四个顺子也类似。

对于后一种，有以下几种转移方法：

• 一组刻子；

• 一组雀头；

• 什么也不选。

然后就是考验代码能力的环节了：

void dp1(int l, int r) {
    for(int i = l; i <= r; ++i)
        for(int j = 0; j <= 4; ++j)
            for(int k = 0; k <= 1; ++k)
                    for(int c1 = 0; c1 <= 4; ++c1)
                        for(int c2 = 0; c2 <= 4; ++c2) {
                                if(!f[i][j][k][c1][c2]) continue ;
                                if(j == 4 && k) chkmax(ans, f[i][j][k][c1][c2]);
                                //刻子*1
                                if(j+1<=4 && cnt[i+1] >= 3)
                                    chkmax(f[i+1][j+1][k][3][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 3) * cbp(i+1, 3));
                                //顺子
                                for(int p = 1; p <= 2; ++p) 
                                    if(j+p<=4 && i>=2 && cnt[i+1]>=p && c1<=cnt[i]-p && c2<=cnt[i-1]-p)
                                        chkmax(f[i+1][j+p][k][p][c1+p], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], p) * C(cnt[i], c1+p) * C(cnt[i-1], c2+p) * cbp(i+1, p) * cbp(i, p) * cbp(i-1, p));
                                //刻子*1+顺子*1
                                if(j+2<=4 && i>=2 && cnt[i+1] >= 4 && c1 < cnt[i] && c2 < cnt[i-1])
                                    chkmax(f[i+1][j+2][k][4][c1+1], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], 4) * C(cnt[i], c1+1) * C(cnt[i-1], c2+1) * cbp(i+1, 4) * cbp(i, 1) * cbp(i-1, 1));
                                //雀头*1
                                if(cnt[i+1] >= 2 && !k)
                                    chkmax(f[i+1][j][1][2][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 2) * cbp(i+1, 2));
                                //雀头*1 + 顺子*1
                                if(j+1<=4 && i>=2 && cnt[i+1] >= 3 && !k && c1 < cnt[i] && c2 < cnt[i-1])
                                    chkmax(f[i+1][j+1][1][3][c1+1], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], 3) * C(cnt[i], c1+1) * C(cnt[i-1], c2+1) * cbp(i+1, 3) * cbp(i, 1) * cbp(i-1, 1));
                                chkmax(f[i+1][j][k][0][c1], f[i][j][k][c1][c2]);
                                //雀头*1 + 顺子*2
                                if(j+2<=4 && i>=2 && cnt[i+1] >= 4 && !k && c1 < cnt[i]-1 && c2 < cnt[i-1]-1)
                                    chkmax(f[i+1][j+2][1][4][c1+2], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], 4) * C(cnt[i], c1+2) * C(cnt[i-1], c2+2) * cbp(i+1, 4) * cbp(i, 2) * cbp(i-1, 2));
                                chkmax(f[i+1][j][k][0][c1], f[i][j][k][c1][c2]);
                            }
}
void dp2(int l, int r) {
	for(int i = l; i <= r; ++i)
		for(int j = 0; j <= 4; ++j)
			for(int k = 0; k <= 1; ++k)
					for(int c1 = 0; c1 <= 4; ++c1)
						for(int c2 = 0; c2 <= 4; ++c2) {
								if(!f[i][j][k][c1][c2]) continue ;
								if(j == 4 && k) chkmax(ans, f[i][j][k][c1][c2]), chkmax(sumq1, f[i][j][k][c1][c2]);
								//刻子           
								if(j+1 <= 4 && cnt[i+1] >= 3)
									chkmax(f[i+1][j+1][k][3][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 3) * cbp(i+1, 3));
								//雀头 
								if(cnt[i+1] >= 2 && !k)
									chkmax(f[i+1][j][1][2][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 2) * cbp(i+1, 2));
								chkmax(f[i+1][j][k][0][c1], f[i][j][k][c1][c2]);
						}
}

处理当前询问的部分有关「$[3\times 4+2]$」的：

	f[0][0][0][0][0] = 1;
	dp1(0, 8);
	dp2(9, 10);
	dp1(11, 17);
	dp2(18, 19);
	dp1(20, 26);
	dp2(27, 33);
	for(int c1 = 0; c1 <= 4; ++c1)
		for(int c2 = 0; c2 <= 4; ++c2)
			chkmax(ans, f[34][4][1][c1][c2]);

• 「七对子」

和上面的类似，不过更为简单。

设 $g_{i,j}$ 为前 $i$ 种牌，$j$ 个雀头，的最高分数。

由于需要不同的雀头，对于一种牌，只能选出一组雀头。

这样转移就很好转移了。

	g[0][0] = 7;
	for(int i = 0; i <= 33; ++i)
		for(int j = 0; j <= 7; ++j) {
			if(!g[i][j]) continue ;
			if(j == 7) chkmax(ans, g[i][j]);
			if(cnt[i+1] >= 2 && j+1 <= 7)
				chkmax(g[i+1][j+1], g[i][j] * C(cnt[i+1], 2) * cbp(i+1, 2));
			chkmax(g[i+1][j], g[i][j]);
		}
	chkmax(ans, g[34][7]);

总得来讲，我写这道题大体分为这三步：

1. 整理题目规则，写一份"攻略"，标出重点，坑点，例如该题中顺子的条件，「七对子」要求雀头都不相等。

2. 分析题目哪些是不必要写的，剩下几部分分别应该怎么解决。

3. 编写代码，尽量封装来减少代码量，使代码可读性更高，更好调试。

希望能对你有所帮助。

完整版代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define pb push_back
#define fir first
#define sec second
#define mp std::make_pair
typedef std::pair<int, int> pii;
typedef long long ll;
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T Abs(T x) { return x < 0 ? -x : x; }
template <typename T> T chkmax(T &x, T y) { return x = x > y ? x : y; }
template <typename T>
T &read(T &r) {
    r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
    while(ch >= '0' && ch <= '9') r = (r << 3) + (r <<1) + (ch ^ 48), ch = getchar();
    return r = w ? -r : r;
}

bool baopai[35];
int cnt[35];

namespace Calc {
    int fac[15], pow2[50];
    void Cpre() { fac[0] = 1; for(int i = 1; i <= 10; ++i) fac[i] = fac[i-1] * i; pow2[0] = 1; for(int i = 1; i <= 30; ++i) pow2[i] = pow2[i-1]*2; }
    inline ll C(int x, int y) { return fac[x] / fac[y] / fac[x-y]; }
    inline ll cbp(int x, int y) { return baopai[x] ? pow2[y] : 1; }
}
using namespace Calc;
namespace How_to_get {
    inline char getcha() { char ch; std::cin >> ch; return ch; }          
    inline int getpai() {
        char ch = getcha(); if(ch == '0') return 0;
        if(ch >= '1' && ch <= '9') {
            char ch2 = getcha();
            if(ch2 == 'm') return ch-'0';
            if(ch2 == 'p') return 9+(ch-'0');
            if(ch2 == 's') return 18+(ch-'0');
        }
        switch(ch) {
            case 'E': return 28;
            case 'S': return 29;
            case 'W': return 30; 
            case 'N': return 31; 
            case 'Z': return 32; 
            case 'B': return 33; 
            case 'F': return 34; 
        }
        return 0;
    }
}
using namespace How_to_get;

int gsws[15] = {0, 1, 9, 10, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34};

void read1() {
    int x = getpai();
    while(x) {
        cnt[x]--;
        x = getpai();
    }
}
void read2() {
    int x = getpai();
    while(x) {
        baopai[x] = 1;
        x = getpai();
    }
}
ll Gsws() {
    Cpre();
    ll sumq = 0, mul = 1, bps = 0;
    for(int i = 1; i <= 13; ++i) if(cnt[gsws[i]] == 0) return 0;
    for(int i = 1; i <= 13; ++i) mul *= cnt[gsws[i]], bps += baopai[gsws[i]];
    for(int i = 1; i <= 13; ++i) {
        if(cnt[gsws[i]] <= 1) continue ;
        sumq = Max(sumq, mul / cnt[gsws[i]] * C(cnt[gsws[i]], 2) * pow2[bps+baopai[gsws[i]]]);
    }
    return sumq * 13;
}

ll f[40][10][5][6][6], g[40][10];
ll ans = 0;

    //1  -> 9   1m,2m,3m...
    //10 -> 18  1p,2p,3p...
    //19 -> 27  1s,2s,3s...
    //28:E  29:S  30:W  31:N  32:Z  33:B  34:F 
void dp1(int l, int r) {
    for(int i = l; i <= r; ++i)
        for(int j = 0; j <= 4; ++j)
            for(int k = 0; k <= 1; ++k)
                    for(int c1 = 0; c1 <= 4; ++c1)
                        for(int c2 = 0; c2 <= 4; ++c2) {
                                if(!f[i][j][k][c1][c2]) continue ;
                                if(j == 4 && k) chkmax(ans, f[i][j][k][c1][c2]);
                                //刻子*1
                                if(j+1<=4 && cnt[i+1] >= 3)
                                    chkmax(f[i+1][j+1][k][3][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 3) * cbp(i+1, 3));
                                //顺子
                                for(int p = 1; p <= 2; ++p) 
                                    if(j+p<=4 && i>=2 && cnt[i+1]>=p && c1<=cnt[i]-p && c2<=cnt[i-1]-p)
                                        chkmax(f[i+1][j+p][k][p][c1+p], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], p) * C(cnt[i], c1+p) * C(cnt[i-1], c2+p) * cbp(i+1, p) * cbp(i, p) * cbp(i-1, p));
                                //刻子*1+顺子*1
                                if(j+2<=4 && i>=2 && cnt[i+1] >= 4 && c1 < cnt[i] && c2 < cnt[i-1])
                                    chkmax(f[i+1][j+2][k][4][c1+1], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], 4) * C(cnt[i], c1+1) * C(cnt[i-1], c2+1) * cbp(i+1, 4) * cbp(i, 1) * cbp(i-1, 1));
                                //雀头*1
                                if(cnt[i+1] >= 2 && !k)
                                    chkmax(f[i+1][j][1][2][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 2) * cbp(i+1, 2));
                                //雀头*1 + 顺子*1
                                if(j+1<=4 && i>=2 && cnt[i+1] >= 3 && !k && c1 < cnt[i] && c2 < cnt[i-1])
                                    chkmax(f[i+1][j+1][1][3][c1+1], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], 3) * C(cnt[i], c1+1) * C(cnt[i-1], c2+1) * cbp(i+1, 3) * cbp(i, 1) * cbp(i-1, 1));
                                chkmax(f[i+1][j][k][0][c1], f[i][j][k][c1][c2]);
                                //雀头*1 + 顺子*2
                                if(j+2<=4 && i>=2 && cnt[i+1] >= 4 && !k && c1 < cnt[i]-1 && c2 < cnt[i-1]-1)
                                    chkmax(f[i+1][j+2][1][4][c1+2], f[i][j][k][c1][c2] / C(cnt[i], c1) / C(cnt[i-1], c2) * C(cnt[i+1], 4) * C(cnt[i], c1+2) * C(cnt[i-1], c2+2) * cbp(i+1, 4) * cbp(i, 2) * cbp(i-1, 2));
                                chkmax(f[i+1][j][k][0][c1], f[i][j][k][c1][c2]);
                            }
}
void dp2(int l, int r) {
    for(int i = l; i <= r; ++i)
        for(int j = 0; j <= 4; ++j)
            for(int k = 0; k <= 1; ++k)
                    for(int c1 = 0; c1 <= 4; ++c1)
                        for(int c2 = 0; c2 <= 4; ++c2) {
                                if(!f[i][j][k][c1][c2]) continue ;
                                if(j == 4 && k) chkmax(ans, f[i][j][k][c1][c2]);
                                //刻子           
                                if(j+1 <= 4 && cnt[i+1] >= 3)
                                    chkmax(f[i+1][j+1][k][3][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 3) * cbp(i+1, 3));
                                //雀头 
                                if(cnt[i+1] >= 2 && !k)
                                    chkmax(f[i+1][j][1][2][c1], f[i][j][k][c1][c2] * C(cnt[i+1], 2) * cbp(i+1, 2));
                                chkmax(f[i+1][j][k][0][c1], f[i][j][k][c1][c2]);
                        }
}
void solve() {
    for(int i = 1; i <= 34; ++i) cnt[i] = 4, baopai[i] = 0;
    read1(); read2();
    ans = 0;
    ans = Max(ans, Gsws());
    for(int i = 1; i <= 34; ++i)
        for(int j = 0; j <= 4; ++j)
            for(int k = 0; k <= 1; ++k)
                    for(int c1 = 0; c1 <= 4; ++c1)
                        for(int c2 = 0; c2 <= 4; ++c2)
                                f[i][j][k][c1][c2] = 0;
    for(int i = 1; i <= 34; ++i)
        for(int j = 0; j <= 7; ++j)
                    g[i][j] = 0;
    f[0][0][0][0][0] = 1;
    dp1(0, 8);
    dp2(9, 10);
    dp1(11, 17);
    dp2(18, 19);
    dp1(20, 26);
    dp2(27, 33);
    for(int c1 = 0; c1 <= 4; ++c1)
        for(int c2 = 0; c2 <= 4; ++c2)
            chkmax(ans, f[34][4][1][c1][c2]);
    g[0][0] = 7;
    for(int i = 0; i <= 33; ++i)
        for(int j = 0; j <= 7; ++j) {
            if(!g[i][j]) continue ;
            if(j == 7) chkmax(ans, g[i][j]);
            if(cnt[i+1] >= 2 && j+1 <= 7)
                chkmax(g[i+1][j+1], g[i][j] * C(cnt[i+1], 2) * cbp(i+1, 2));
            chkmax(g[i+1][j], g[i][j]);
        }
    chkmax(ans, g[34][7]);
    printf("%lld\n", ans);
}

signed main() { //freopen("in.txt", "r", stdin);
    int T; read(T);
    while(T--) solve();
    return 0;
}