#include<stdio.h>
#define N 110
#define MAX 0x7fff

int main()
{
    int casenum;
    scanf("%d", &casenum);
    while(casenum --)
    {
        int n; /* 设备组数[1, 100] */
        int m[N]; /* 每一组设备的个数[1, 100] */
        int b[N][N]; /* b[i][j]，第i组第j号设备的带宽 */
        int p[N][N]; /* p[i][j]，第i组第j号设备的费用 */
        int f[500]; /* 滚动数组，f[i, j]表示选取前i组设备带宽为j时的最小费用 */
        int i, j;
        int high, low;
        double maxbp;
        scanf("%d", &n);
        high = 0; low = MAX;
        for(i = 1; i <= n; i ++)
        {
            scanf("%d", &m[i]);
            for(j = 1; j <= m[i]; j ++)
            {
                scanf("%d%d", &b[i][j], &p[i][j]);
                if(b[i][j] > high)
                    high = b[i][j];
                if(b[i][j] < low)
                    low = b[i][j];
            }
        } /* high，low记录当前case的带宽取值范围 */
        for(j = low; j <= high; j ++)
            f[j] = MAX;
        for(i = 1; i <= m[1]; i ++)
            if(f[b[1][i]] > p[1][i])
                f[b[1][i]] = p[1][i];
        /* 上面两个循环将f数组初始化为f[1, j] */
        for(i = 2; i <= n; i ++)
            for(j = low; j <= high; j ++)
            {
                int k, k1, k2, km;
                int min1, min2, min;
                int c1, c2;
                min1 = min2 = MAX;
                k1 = k2 = 0;
                for(k = 1; k <= m[k]; 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];
                    }
                } /* k1是b较大p最小，k2是b相同p最小 */
                if(k1 && f[j] != MAX) /* k1存在且f[i, j]存在，途径一可行 */
                    c1 = f[j] + p[i][k1];
                else
                    c1 = MAX;
                min = MAX;
                km = 0;
                for(k = j + 1; k <= high; k ++)
                    if(f[k] < min)
                    {
                        km = k;
                        min = f[k];
                    } /* km是选择前i-1组设备时带宽大于当前带宽j且费用最小的带宽大小 */
                if(km && k2) /* 途径二可行 */
                    c2 = f[km] + p[i][k2];
                else
                    c2 = MAX;
                f[j] = c1 < c2 ? c1 : c2; /* 从两种途径中选取最小的 */
            }
        maxbp = 0;
        for(j = low; j <= high; j ++)
            if(f[j] != MAX && (double)j / f[j] > maxbp)
                maxbp = (double)j/ f[j];
        printf("%.3f\n", maxbp);
    }
    return 0;
}

/*
f[i][j]表示已选取前i组设备，带宽为j时的最小费用
由f[i - 1][...]转移到f[i][j]有两种途径
一是f[i - 1][j] + min{p[i][k](满足b[i][k] >= j)}（原设备限制带宽为j）
二是min{f[i - 1][t](满足t > j)} + min{p[i][k](满足b[i][k] == j)}（新选取设备限制带宽为j）
*/

• Re:DP自己都晕了，竟然一次AC。。。整理思路贴代码 (15) Aule 2011-10-20 20:35:16