http://www.51nod.com/onlineJudge/questionCode.html#problemId=1450¬iceId=462195
f[i][j]表示玩了前i个游戏,还剩j次必须达到两金币
不是很理解为什么自己推的式子里分子是2
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } const int MAXN=2048; double f[MAXN*2][MAXN]; int n,m; struct Node{ int x,y; bool operator < (const Node &rhs)const{ return y==rhs.y?x>rhs.x:y>rhs.y; } }a[MAXN]; inline void upmin(double &x,double y){ x=min(x,y); } int main(){ n=rd();m=rd(); for(int i=1;i<=n;i++){ a[i].x=rd();a[i].y=rd(); } memset(f,0x7f,sizeof(f)); sort(a+1,a+1+n); m-=n;f[0][m]=0; for(int i=1;i<=n;i++){ double x=a[i].x*1.0,y=a[i].y*1.0,s=x+y; for(int j=0;j<m;j++){ upmin(f[i][j],f[i-1][j]*x/s+f[i-1][j+1]*y/s+1000.0/s); upmin(f[i][j],f[i-1][j+1]+1000.0/y); } upmin(f[i][m],f[i-1][m]+1000.0/s); } printf("%.7lf",f[n][0]); return 0; }