zoj 3022 Watashi and Kimi

zoj 3022 Watashi and Kimi"/>

zoj 3022 Watashi and Kimi

:8080/judge/contest/view.action?cid=11975#problem/I

一道概率题。还是递推题。

用dp[pre][i][j]表示当前有i道正确的题，j道不正确的题。

用dp[now][i][j]表示下一个状态有i道正确的题，j道不正确的题。

如果当前是w同学，那么他有两种选择。

改错一道题，或者不做任何改变。

要是改错的话，他只能从对的里面选一道。如果要是不动的话那么他将会从错的题里面选择，而且选择的错的题不能是之前改过的。所以状态如下

if(i>0)
dp[now][i-1][j+1]+=dp[pre][i][j]*i/(n-stepw);
dp[now][i][j]+=dp[pre][i][j]*(j-stepw)/(n-stepw);
}

同理k同学的道理是一样的

if(j>0)
dp[now][i+1][j-1]+=dp[pre][i][j]*j/(n-stepk);
dp[now][i][j]+=dp[pre][i][j]*(i-stepk)/(n-stepk);

如果之前k同学或者w同学已经连续改了n题，那么要跳出，没题目让他改了。跳出后，因为下个状态还没有算出。这时没有下一个状态和上一个状态没有任何改变，所以直接复制

（尼玛我们memcpy写成memcmp，结果wa的要死。。。）

用的是滚动数组。

pre和now是两把指针。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
double dp[2][20][20];
int pre,now;
int n;
double solve()
{//cout<<"^^^^"<<endl;pre=0;now=1;//dp[pre][n][0]=1;char who[20];int stepw=0;int stepk=0;int i,j;memset(dp,0,sizeof(dp));dp[pre][n][0]=1;while(cin>>who){//cout<<who<<"@@@@"<<endl;if(who[0]=='E')break;elsefor( i=0;i<=n;i++){j=n-i;if(who[0]=='W'){if(stepw>=n)break;if(i>0)dp[now][i-1][j+1]+=dp[pre][i][j]*i/(n-stepw);//还有正确的题目就该，从正确的里面选dp[now][i][j]+=dp[pre][i][j]*(j-stepw)/(n-stepw);//不动，从错误的里面选。不能选之前的}elseif(who[0]=='K'){if(stepk>=n)break;if(j>0)dp[now][i+1][j-1]+=dp[pre][i][j]*j/(n-stepk);//还有错误的题目就该，从正确的里面选dp[now][i][j]+=dp[pre][i][j]*(i-stepk)/(n-stepk);//不动，从正确的里面选。不能选之前的}/* for(int l=0;l<2;l++){for(int k=0;k<=n;k++){for(int o=0;o<=n;o++)cout<<dp[l][k][o]<<" ";cout<<endl;}cout<<endl;}*/}if(i!=n+1)memcpy(dp[now],dp[pre],sizeof(dp[0]));//是memcpy啊不是memcmpif(who[0]=='W')stepw++,stepk=0;elseif(who[0]=='K')stepk++,stepw=0;swap(pre,now);//交换指针memset(dp[now],0,sizeof(dp[now]));}return dp[pre][n][0];
}int main()
{while(cin>>n){getchar();printf("%.2lf\n",solve());}return 0;
}

转载于:.html