zoj 3605

佚名 6年前 (2019-04-12) 随笔 1239人围观抢沙发百度已收录

链接

[https://vjudge.net/contest/293343#problem/F]

题意

就是有n碗，有一个宝石，知道开始宝石在那个碗下面
进行M次交换，但知道其中的k次，问你最可能在那个碗

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

分析

概率dp
状态定义；dp[i][j][r];
当前进行i次知道其中j次宝石在第r碗的方案数
最后就是就是进行m知道K次的方案数最多的那个碗
状态转移：
具体看代码吧

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll 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;
}