首页 > 代码库 > zoj3605 Find the Marble --- 概率dp
zoj3605 Find the Marble --- 概率dp
n个杯子,球最开始在s位置,有m次换球操作,看到了k次,看的人根据自己看到的k次猜球最终在哪个位置,输出可能性最大的位置。
dp[m][k][s]表示前m次操作中看到了k次球最终在s的频率。
#include<cstdio> #include<cstring> int n,m,k,s,x[55],y[55]; long long dp[55][55][55]; int main() { int i,j,l,T; scanf("%d",&T); while (T--) { scanf("%d%d%d%d",&n,&m,&k,&s); for (i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]); memset(dp,0,sizeof dp); dp[1][0][s]=1;//初始状态就是球本身的位置 for (i=1;i<=m;i++) for (j=0;j<=k;j++) for (l=1;l<=n;l++) { if(dp[i][j][l]) { dp[i+1][j][l]+=dp[i][j][l];//没看到这次 //看到了这次 if (l==x[i]) dp[i+1][j+1][y[i]]+=dp[i][j][l]; else if (l==y[i]) dp[i+1][j+1][x[i]]+=dp[i][j][l]; else dp[i+1][j+1][l]+=dp[i][j][l];//这里也要j+1呀 就是看到了这次交换但没有任何影响 } } int ans=1; for (i=2;i<=n;i++) if (dp[m+1][k][ans]<dp[m+1][k][i]) ans=i; printf("%d\n",ans); } return 0; }
zoj3605 Find the Marble --- 概率dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。