 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
DP题解#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 999999
#define N 501
#define M 101
using namespace std;
int m[M],b[M][M],p[M][M],f[N];
int main()
{
int nn;
scanf("%d",&nn);
int n,Min,Max;
int k1,k2,km;
int min1,min2,MIN;
int c1,c2;
double ans;
while (nn--)
{
scanf("%d",&n);
Max=-INF;
Min=INF;
for (int i=1;i<=n;i++)
{
scanf("%d",&m[i]);
for (int j=1;j<=m[i];j++)
{
scanf("%d%d",&b[i][j],&p[i][j]);
if (b[i][j]<Min) Min=b[i][j];
if (b[i][j]>Max) Max=b[i][j];
}
}
for (int i=Min;i<=Max;i++) f[i]=INF;
for (int i=1;i<=m[1];i++)
if (f[b[1][i]]>p[1][i]) f[b[1][i]]=p[1][i];
for (int i=2;i<=n;i++)
for (int j=Min;j<=Max;j++)
{
min1=min2=INF;
k1=k2=0;
for (int k=1;k<=m[i];k++)
{
if(b[i][k]>=j&&p[i][k]<min1)
{
k1=k;
min1=p[i][k];
}
if(b[i][k]==j&&p[i][k]<min2)
{
k2=k;
min2=p[i][k];
}
}
if(k1&&f[j]!=INF) c1=f[j]+p[i][k1];
else c1=INF;
MIN=INF;
km=0;
for(int k=j+1;k<=Max;k++)
if(f[k]<MIN)
{
km=k;
MIN=f[k];
}
if(km&&k2) c2=f[km]+p[i][k2];
else c2=INF;
f[j]=c1<c2?c1:c2;
}
ans=0;
for (int i=Min;i<=Max;i++)
if ((f[i]!=INF)&&((double)i/f[i]>ans)) ans=(double)i/f[i];
printf("%.3lf\n",ans);
}
return 0;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
