| ||||||||||
| 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