目录
题目描述:
在某个游戏中有一个骰子游戏。在游戏中，你需要投掷 5 个标准六面骰子（骰子为一个正方体，6 个面上分别有1、2、3、4、5、6中的一个数字，骰子的质量均匀），投出的点数根据组合会获得一个“获胜等级”。获胜等级从高到低如下：
- 五个同点数 - 五个骰子显示相同的点数
- 四个同点数 - 四个骰子显示相同的点数
- 葫芦 - 一对和一个三个同点数（如1、1、3、3、3）
- 六高顺子 - 投出的点数为 2、3、4、5、6
- 五高顺子 - 投出的点数为 1、2、3、4、5
- 三个同点数 - 三个骰子显示相同的点数（如1、1、1、2、3）
- 两对 - 投出的点数中有两对是相同的（如 1、1、2、2、3）
- 一对 - 投出的点数有一对是相同的（如 1、1、2、3、4）
- 无 - 除去以上的其他情况
给定你已经投出的一次结果，现在假设你可以选择任意个骰子重投一次，请问怎么样操作，才能最大化在重骰后获得更好的获胜等级的概率呢？
注意：更好的获胜等级需要严格地比当前的获胜等级更好，例如 1、1、2、2、3 如果重骰后变为 1、1、3、3、4 并不比当前的获胜等级更好。
输入格式:
输入第一行是一个正整数 T (1≤T≤10)，表示接下来有多少组数据。
每组数据只有一行 5 个数字，表示第一次投出的 5 个骰子的点数。
输出格式:
对于每组数据输出三个整数，其中第一个整数为为了获得最大的概率需要重新骰几个骰子，后面的两个整数为重骰骰子后概率的最简分数，其中第二个整数为分子，第三个整数为分母。如果分子为 0，分母为 1。
如果有多种获得最大概率的情况，取重骰的骰子数最少的方案。
输入样例:
3
1 1 2 2 3
1 1 2 3 4
1 1 1 2 3输出样例:
3 4 9
3 13 18
2 4 9
样例说明:
样例的第一组数据中，一种方案是：重骰最后三个骰子以获得最大的概率（只要重骰的有一个“1”或者三个均相等即可）。
解题思路(DFS)
总体利用两重dfs，遍历所有可能的重投情况。
第一层：枚举所有可能重投的骰子个数和这些重投骰子的所在位置
第二层：对第一层确定的情况进行模拟投掷的过程，遍历所有重投后的情况，并计算符合条件（重投之后等级严格高于初始等级的情况）情况数量/概率，计算在第一层枚举的个数和位置的情况下重投后的最优解。
最后确定全局最优解。
完整代码（C++）
#include<bits/stdc++.h>
using namespace std;
#define int long long
int num[6],cnt[7];
vector<int>v;//存储重投骰子位置
int ranks;//初始状态等级
bool vis[6];
int resdm=1,resmole,mole;//当前最优分母、当前最优分子、符合条件情况数
int ans1,ans2,ans3=1;//重投个数、全局最优分子、全局最优分母
//判断当前属于哪个等级
int check(){
memset(cnt,0,sizeof cnt);
for(int i=1;i<=5;i++)cnt[num[i]]++;
//1级：五个同点数 - 五个骰子显示相同的点数
if(cnt[1]==5||cnt[2]==5||cnt[3]==5||cnt[4]==5||cnt[5]==5||cnt[6]==5) return 1;
//2级：四个同点数 - 四个骰子显示相同的点数
if(cnt[1]==4||cnt[2]==4||cnt[3]==4||cnt[4]==4||cnt[5]==4||cnt[6]==4) return 2;
//3级：葫芦 - 一对和一个三个同点数
if(cnt[1]==3||cnt[2]==3||cnt[3]==3||cnt[4]==3||cnt[5]==3||cnt[6]==3)
if(cnt[1]==2||cnt[2]==2||cnt[3]==2||cnt[4]==2||cnt[5]==2||cnt[6]==2)
return 3;
//4级：六高顺子 - 投出的点数为 2、3、4、5、6
if(cnt[2]==cnt[3]&&cnt[3]==cnt[4]&&cnt[4]==cnt[5]&&cnt[5]==cnt[6])return 4;
//5级：五高顺子 - 投出的点数为 1、2、3、4、5
if(cnt[1]==cnt[2]&&cnt[2]==cnt[3]&&cnt[3]==cnt[4]&&cnt[4]==cnt[5])return 5;
//6级：三个同点数 - 三个骰子显示相同的点数
if(cnt[1]==3||cnt[2]==3||cnt[3]==3||cnt[4]==3||cnt[5]==3||cnt[6]==3) return 6;
//7/8级：两/一对 - 投出的点数中有两/一对是相同的
if(cnt[1]==2||cnt[2]==2||cnt[3]==2||cnt[4]==2||cnt[5]==2||cnt[6]==2){
int t=0;
for(int i=1;i<=6;i++)
if(cnt[i]==2)
t++;
if(t==2)return 7;
else return 8;
}
//无 - 除去以上的其他情况
return 9;
}
void dfs_2(int u,int n){
if(u==n){
int now_rank=check();
if(now_rank<ranks){ //比初始等级高的情况
mole++; //符合条件情况数++
}
return;
}
//模拟投掷的6种情况
for(int i=1;i<=6;i++){
int t = num[v[u]];
num[v[u]] = i;
dfs_2(u+1,n);
num[v[u]] = t;
}
}
void dfs_1(int u,int n){
if(u==n){
//计算当前选择的n个位置骰子重投后的等级比初始高的情况数
mole=0;
dfs_2(0,n);
//计算分母
int dm = pow(6,n);
//和本次dfs中最优概率比较
if(mole*resdm >= resmole*dm){
resmole = mole;
resdm = dm;
}
return;
}
//枚举选择第i个位置的骰子进行重投
for(int i=1;i<=5;i++){
if(vis[i])continue;
vis[i]=1;
v.push_back(i);
dfs_1(u+1,n);
v.pop_back();
vis[i]=0;
}
}
void solve(){
for(int i=1;i<=5;i++)cin>>num[i];
ranks=check();
//最高级别，不需要重投了
if(ranks==1){
cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
return;
}
//枚举选择重投的骰子的个数 一定从大到小！！！（深受其害）
for(int i=4;i>=1;i--){
dfs_1(0,i);
//求得最优解
if(resmole*ans3 >= ans2*resdm){
ans1 = i;
ans2 = resmole;
ans3 = resdm;
}
resmole = 0;
resdm = 1;
}
//偷个懒，用__gcd()
cout<<ans1<<" "<<ans2/__gcd(ans2,ans3)<<" "<<ans3/__gcd(ans2,ans3)<<endl;
ans1=ans2=0;
ans3=1;
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}