BZOJ1419:Red is good 期望dp
思路:
令\(f_{i,j}\)表示目前还剩\(i\)张红牌,\(j\)张黑牌时的期望最优利益.
有几种情况:
当\(i=0\)时,\(f_{i,j}=0\);
当\(j=0\)时,\(f_{i,j}=i\);
否则\(f_{i,j}=max(0,\frac{i}{i+j}(1+f_{i-1,j})+\frac{j}{i+j}(-1+f_{i,j-1}))\)
上面的概率枚举的是最上面一张牌的颜色.这应该很容易理解.
那么我们可以记忆化搜索,时间\(O(n^2)\),空间\(O(n^2)\).(MLE)
所以只能递推来做到\(O(n)\)的空间.
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; #define N 5010 typedef double f2; f2 f[2][N<<1]; f2 Max(f2 a,f2 b){if(a>b)return a;else return b;} f2 solve(int n,int m){ int now=0,lst=1; for(int i=1;i<=n+m;++i,now^=1,lst^=1){ for(int j=0;j<=n&&j<=i;++j){ if(!j)f[now][j]=0;else{if(j==i)f[now][j]=j;else f[now][j]=Max(0,(f[lst][j-1]+1)*j/i+(f[lst][j]-1)*(i-j)/i);} } }return f[lst][n]; } int main(){ int n,m;cin>>n>>m; f2 res=solve(n,m); long long count=(long long)(res*1000000); printf("%lld.%06lld",count/1000000,count%1000000); return 0; }
Apr 23, 2023 07:33:25 PM
crediblebh