LightOJ-1342 Aladdin and the Magical Sticks(期望dp)

题解：期望dp。设不可分辨的木棍个数为n1，平均权值为tot1,可分辨的木棍个数为n2，平均权值为tot2
对于dp[i][j]，表示已拿过i个不可分辨的木棍和j个可分辨的木棍，那么还剩sum=n1+n2-j个木棍
dp[i][j]=(n1-i)/sum*(dp[i+1][j]+tot1)+(n2-j)sum*(dp[i][j+1]+tot2)+i/sum*(dp[i][j]+tot1)


因为题中n<=5000,不能开5000*5000的数组，考虑到i的状态只与i和i+1有关，所以用滚动数组

#include<bits/stdc++.h>
using namespace std;
const int MX = 5005;
double dp[2][MX];
int main(){int T,n,n1,n2;//  freopen("in.txt","r",stdin);scanf("%d",&T);for(int cas=1;cas<=T;cas++){n1=n2=0;scanf("%d",&n);double tot1=0,tot2=0;for(int i=0;i<n;i++) {int a,b;scanf("%d%d",&a,&b);if(b==1) tot2+=a,n2++;else tot1+=a,n1++;}if(n1)tot1/=n1;if(n2)tot2/=n2; for(int i=n1;i>=0;i--){memset(dp[i%2],0,sizeof(dp[i%2]));for(int j=n2;j>=0;j--){if(i==n1&&j==n2) continue;int sum=n-j;dp[i%2][j]=(n1-i)*dp[(i+1)%2][j]/sum+n1*tot1/sum;dp[i%2][j]+=(n2-j)*(dp[i%2][j+1]+tot2)/sum;dp[i%2][j]=dp[i%2][j]*sum/(sum-i);}}printf("Case %d: %.7f\n",cas,dp[0][0]);}return 0;
}

N - Aladdin and the Magical Sticks

  LightOJ - 1342