链接

[]

题意

就是有n碗，有一个宝石，知道开始宝石在那个碗下面

进行M次交换，但知道其中的k次，问你最可能在那个碗

分析

概率dp

状态定义；dp[i][j][r];

当前进行i次知道其中j次宝石在第r碗的方案数

最后就是就是进行m知道K次的方案数最多的那个碗

状态转移：

具体看代码吧

代码

#include
    
     using namespace std;#define ll long longll dp[60][60][60];int t,n,m,k,s;int main(){    scanf("%d",&t);    while(t--){        memset(dp,0,sizeof(dp));        scanf("%d%d%d%d",&n,&m,&k,&s);        dp[0][0][s]=1;        int x,y;        for(int i=1;i<=m;i++){//当前操作次数          scanf("%d%d",&x,&y);            for(int j=1;j<=n;j++){//当前位置                for(int r=0;r<=k;r++)//知道的次数                 {                    if(r!=0){                        if(x==j)                        dp[i][r][j]+=dp[i-1][r-1][y];                        else if(y==j)                        dp[i][r][j]+=dp[i-1][r-1][x];                        else dp[i][r][j]+=dp[i-1][r-1][j];                    }                    dp[i][r][j]+=dp[i-1][r][j];                }            }        }        int flag; ll ma=-1;        for(int i=1;i<=n;i++)            if(dp[m][k][i]>ma){               ma=dp[m][k][i];               flag=i;              }            printf("%d\n",flag);    }    return 0;}