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 |
一次过了。。。。。。。。。。。难得啊#include <stdio.h> #include <iostream> #include <string.h> #define M 10000 using namespace std; int f[101][M]; bool hash[M]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; int b,p; int max=0; scanf("%d",&n); memset(f,1000000,sizeof(f)); memset(hash,false,sizeof(hash)); for(int i=0;i<M;i++) f[0][i]=0; for(int i=1;i<=n;i++) { scanf("%d",&m); for(int j=0;j<m;j++) { scanf("%d%d",&b,&p); hash[b]=true; if(max<b)max=b; for(int k=b;k<M;k++) f[i][b]=(f[i-1][k]+p)<f[i][b]?(f[i-1][k]+p):f[i][b]; for(int k=0;k<b;k++) if(f[i-1][k]+p<f[i][k])f[i][k]=f[i-1][k]+p; } } float ans=0; for(int i=1;i<=max;i++) if(f[n][i]>0&&hash[i]&&i/(float)f[n][i]>ans)ans=i/(float)f[n][i]; printf("%.3f\n",ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator