本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-31 13:35:49

Solution

算法标签： 动态规划。

考虑三进制状压，令 $0$ 表示出石头，$1$ 表示出布，$2$ 表示出剪刀。令 $f_{i,j,k}$ 表示对于出招方式 $j$，前 $i$ 轮获胜 $-$ 失败等于 $k$ 且 $i+1\sim m$ 轮强制钦定与 $j$ 出招方式一样。转移分讨第 $i$ 轮对局情况（令 $x$ 为第 $i$ 轮出的方式）：

1. 获胜：第 $i$ 轮高适只能出 $(x+2)\bmod 3$，所以从对应的 $f_{i-1,j-3^ix+3^i(x+2)\bmod 3,k-1}$ 转移而来，因为这样强制钦定第 $i$ 位是 $(x+2)\bmod 3$，从而保证获胜。
2. 平局：第 $i$ 轮高适只能出 $x$，所以从 $f_{i-1,j,k}$ 转移而来。
3. 失败：第 $i$ 轮高适只能出 $(x+1)\bmod 3$，所以从对应的 $f_{i-1,j-3^ix+3^i(x+1)\bmod 3,k+1}$ 转移而来。

时间复杂度：$O(3^m m^2)$。

Code

#include <bits\/stdc++.h>
using namespace std;
using i64 = long long;

const double eps = 1e-10;

int n, m;
int pw[13];
double dp[2][531441][25];

int get(string x) {
	if (x == "rock") return 0;
	else if (x == "paper") return 1;
	else return 2;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;
	pw[0] = 1;
	for (int i = 1; i <= m; i ++)
		pw[i] = pw[i - 1] * 3;

	for (int i = 1; i <= n; i ++) {
		string out;
		double p;
		cin >> p;
		int mask = 0;
		for (int j = 0; j < m; j ++)
			cin >> out, mask += pw[j] * get(out);
		dp[0][mask][m] += p;
	}

	for (int j = 1; j <= m; j ++)
		for (int i = 0; i < pw[m]; i ++)
			for (int k = 0; k <= 2 * m; k ++) {
				dp[j & 1][i][k] = dp[(j - 1) & 1][i][k]; \/\/ 第 j 轮平局
				int out = i \/ pw[j - 1] % 3;
				\/\/ 第 j 轮获胜
				if (k) dp[j & 1][i][k] += dp[(j - 1) & 1][i - out * pw[j - 1] + (out + 2) % 3 * pw[j - 1]][k - 1];
				\/\/ 第 j 轮失败
				if (k + 1 < 2 * m) dp[j & 1][i][k] += dp[(j - 1) & 1][i - out * pw[j - 1] + (out + 1) % 3 * pw[j - 1]][k + 1];
			}

	double res = -1;
	int mask;
	vector<pair<string, int>> ord;
	for (int i = 0; i < pw[m]; i ++) {
		string temp;
		for (int j = 0; j < m; j ++)
			temp += char((i \/ pw[j] % 3) + '0');
		ord.push_back({temp, i});
	}
	sort(ord.begin(), ord.end());

	for (auto [t, i] : ord) {
		double sum = 0;
		for (int j = m; j <= 2 * m; j ++)
			sum += dp[m & 1][i][j];
		if (sum > res + eps)
			res = sum, mask = i;
	}

	printf("%.6lf\n", res);
	for (int i = 0; i < m; i ++)
		if (mask \/ pw[i] % 3 == 0) printf("rock ");
		else if (mask \/ pw[i] % 3 == 1) printf("paper ");
		else printf("scissors ");
	printf("\n");

	return 0;
}