| ||||||||||
| 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 | |||||||||
本菜鸟用N^4的DPWA了。。。附带菜鸟程序,请大牛指点!#include<iostream>
using namespace std;
int band[10000];
int f[100][10000];
struct node
{
int b, c;
} que[100][100];
int main()
{
int t, n;
int num[100];
scanf("%d", &t);
for (int r = 0; r != t; r ++)
{
scanf("%d", &n);
int total = 0;
for (int i = 0; i != n; i ++)
{
scanf("%d", &num[i]);
for (int j = 0; j != num[i]; j ++)
{
scanf("%d%d", &que[i][j].b, &que[i][j].c);
band[total] = que[i][j].b;
total ++;
}
}
sort(band, band + total);
double best = 0.0, save;
for (int i = 0; i != n; i ++)
for (int j = 0; j != total; j ++)
{
f[i][j] = -1;
for (int k = 0; k != num[i]; k ++)
if ((que[i][k].b >= band[j]) && ((que[i][k].c < f[i][j]) || (f[i][j] == -1)))
f[i][j] = que[i][k].c;
if ((i > 0) && (f[i][j] != -1))
f[i][j] += f[i - 1][j];
if (f[i][j] > 0)
save = double(band[j]) / double(f[i][j]);
else
save = -1;
if ((i == n - 1) && (save > 0) && (save > best))
best = save;
}
printf("%.3lf\n", best);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator