Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

本菜鸟用N^4的DPWA了。。。附带菜鸟程序,请大牛指点!

Posted by FailedWing at 2007-03-21 10:31:39 on Problem 1018
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator