http://acm.pku.edu.cn/JudgeOnline/problem?id=1018
Код:
#include <stdio.h> #include <string.h> #define MAXN 10010 int f[2][MAXN]; int dev[MAXN]; int task; int n,m,t; int main() { int i,j,k,l,p,q; float h; scanf("%d",&task); while (task--) { scanf("%d",&n); memset(f,-1,sizeof(f)); dev[0] = 2147473647; f[0][0] = 0; t = 0; for (i = 1; i <= n; i++) { scanf("%d",&m); p = t; for (j = 1; j <= m; j++) { t++; scanf("%d%d",&dev[t],&k); for (l = 0; l <= p; l++) { if (f[0][l] == -1) continue; if (dev[l] > dev[t]) q = t; else q = l; if (f[0][l] + k < f[1][q] || f[1][q] == -1) f[1][q] = f[0][l] + k; } } memcpy(f[0],f[1],sizeof(f[0])); memset(f[1],-1,sizeof(f[1])); } h = 0; for (i = 0; i <= t; i++) if (f[0][i] > -1) if ((float)dev[i] / (float)f[0][i] > h) h = (float)dev[i] / (float)f[0][i]; printf("%.3f\n",h); } return 0; }