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