Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
AC (/≧▽≦)/#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<string.h> #include<map> #include<math.h> #include<vector> #include<queue> #include<stack> #define inf 99999999 using namespace std; int t,m,n=0,a[110],b[110][110],p[110][110]; int f[110][1010]; int main() { cin>>t; while(t--) { cin>>m; n=0; for(int i=1;i<=m;i++) { cin>>a[i]; for(int j=1;j<=a[i];j++) { cin>>b[i][j]>>p[i][j]; n=max(n,b[i][j]); } } memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++) f[0][i]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=a[i];k++)if(j<=b[i][k]) f[i][j]=min(f[i][j],f[i-1][j]+p[i][k]); double maxs=0; for(int j=1;j<=n;j++) maxs=max(maxs,j*1.0/f[m][j]); printf("%.3f\n",maxs); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator