第一行两个个整数N，M，且1<=N<=2000，N <= M <= 2N
接下来N行，每行两个整数,X[i]、Y[i]，其中1<=X[i],Y[i],且X[i]+Y[i]<=1000
一个浮点数，即期望E。确保E的精度与正解的绝对误差或相对误差小于1e-7。
2 3
500 500
500 500
2.5
数学问题 期望DP
充满迷惑地过了一题。
根据多年的游戏经验，我们应该先过掉所有的关，然后挑两星概率最大的还没过的关使劲儿怼。
由此我们将关卡按Y排序，先决策Y大的。
设f[i][j]表示还有i关要打，还剩j颗星要拿。
然后愉快地转移。
注释掉的代码是第一次写的版本，看上去很有道理但是只能过一半的点，输出结果和答案比较像，但是精度达不到1e-7
实际运行的版本借鉴了隔壁sdfzyhx的思路，先将m-=n以保证每关必过。
但是这不科学啊，我觉得我的写法也能保证每关必过啊？ 就很迷茫
挣扎了一个小时，放弃了思考。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int INF=0x3f3f3f3f; 8 const int mxn=4005; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 int n,m; 16 double f[mxn][mxn]; 17 struct node{ 18 int x,y; 19 bool operator < (const node &b)const{ 20 return y<b.y; 21 } 22 }a[mxn]; 23 int main(){ 24 int i,j; 25 n=read();m=read(); 26 for(i=0;i<n;i++){ 27 a[i].x=read();a[i].y=read(); 28 } 29 m-=n;// 30 sort(a,a+n); 31 for(i=0;i<=n;i++) 32 for(j=0;j<=m;j++) 33 f[i][j]=INF; 34 f[n][m]=0; 35 for(i=n-1;i>=0;i--){ 36 for(j=0;j<m;j++){ 37 f[i][j]=min(f[i][j], 38 1000.0/(a[i].x+a[i].y)+f[i+1][j]*a[i].x/(a[i].x+a[i].y)+ 39 f[i+1][j+1]*a[i].y/(a[i].x+a[i].y) 40 ); 41 f[i][j]=min(f[i][j],f[i+1][j+1]+1000.0/a[i].y); 42 } 43 f[i][m]=min(f[i][m],1000.0/(a[i].x+a[i].y)+f[i+1][m]); 44 } 45 /* 46 for(i=n-1;i>=0;i--){ 47 for(j=m;j>=0;j--){ 48 f[i][j]=min(f[i][j], 49 1000.0/(a[i].x+a[i].y)+f[i+1][j+1]*a[i].x/(a[i].x+a[i].y)+ 50 f[i+1][j+2]*a[i].y/(a[i].x+a[i].y)); 51 f[i][j]=min(f[i][j],f[i+1][j+2]+1000.0/a[i].y); 52 } 53 f[i][0]=min(f[i][0],1000.0/(a[i].x+a[i].y)+f[i+1][0]); 54 } 55 */ 56 printf("%.7f\n",f[0][0]); 57 return 0; 58 }
原文：http://www.cnblogs.com/SilverNebula/p/7140653.html