首页 > 代码库 > 【期望DP】BZOJ2134- 单选错位

【期望DP】BZOJ2134- 单选错位

2024-08-15 10:19:09   217人阅读

【题目大意】

有n道题，第i道题有ai个选项。一个人把所有的正确答案填到了后面一题上（特殊的，当i=n的时候填到1上），问他期望做对几道题？

【思路】

沙茶题……显然每道题的期望是独立的。

对于某道题，它做对的概率等于当前题目和下一题答案是一样的概率。考虑选项数较小的那一个，它和另一题答案相同的概率=1/另外一道题的选项。

所以dp[i]=1/max(a[i],a[i+1])

over~

 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int MAXN=10000000+50; 5 int a[MAXN]; 6 double ans; 7 int n,A,B,C; 8  9 void init()10 {11     scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);12     for (int i=2;i<=n;i++) a[i]=((ll)a[i-1]*A+B)%100000001;13     for (int i=1;i<=n;i++) a[i]=a[i]%C+1;14 }15 16 void solve()17 {18     ans=0;19     for (int i=1;i<=n;i++)20     {21         double x=(double)a[i]*1.0,y=(double)a[i%n+1]*1.0;22         ans+=1.0/max(x,y);23     }24     printf("%.3f\n",ans);25 }26 27 int main()28 {29     init();30     solve();31     return 0;32 }

 

【期望DP】BZOJ2134- 单选错位


联系
我们