poj1018

먼저 하나의 상태 dp[i]를 정의하여 i번째 물품을 처리한다. 그러나 i번째 물품의 이동은 앞의 물리에 따라 후효성이 없는 원칙에 위배되기 때문에 한 상태를 정의하여 i번째 물품을 처리할 때 앞의 i-1개 물품의 최소 대역폭을 표시해야 한다.
그러면 dp[i][j]는 무엇을 의미할까요?처음에는 앞의 2차원 상태의 대표를 생각했지만 dp[i][j]가 무엇을 대표해야 할지 생각하지 못했다.마땅한 생각은 최소 대역폭이 표시된 이상 최대 B/P를 구하기 위해서는 B가 이미 알고 있다는 것이다.그래서 우리
dp[i][j]는 제I품 처리를 대표하고 최소 대역폭은 j의 최소 총 가격이다. 최소 대역폭은 입력 장치에서만 얻을 수 있기 때문에 dp[i][j]=-1로 최소 대역폭이 없다는 것을 표시해야 한다.그러면 상태 방정식은 dp[i][j]=min(dp[i-1][k]+price[k])(그중 dp[i-1][k]가 우선이기 때문에
도달할 수 있다. 그리고 도달한 후에 상태의 이동을 진행하면 dp[i][k]로 이동할 수 있다. 만약에 m제품 제품의 대역폭이 이 최소 대역폭보다 크거나 dp[i][min]로 이동하면 m제품 대역폭이 최소 대역폭보다 작다는 뜻이다.마지막으로 가능한 모든 최소 대역폭을 열거하여
그중의 최대치.

#include <stdio.h>
#include <string.h>


#define MAX_NUMBER 105
#define MAX_BANDWIDTH 10005
#define min(a, b) ((a) > (b))?(b) : (a)
#define max(a, b) ((a) > (b))?(a) : (b)

int dp[MAX_NUMBER][MAX_BANDWIDTH];
int bandwidth[MAX_NUMBER];
int price[MAX_NUMBER];


int main() {

    int test_case;
    int i, j, k, device_number, manufacture, max_bandwidth, min_number;
    double ans, temp;
    scanf("%d", &test_case);
    while (test_case--) {
        memset(dp, -1, sizeof(dp));
        scanf("%d", &device_number);
        max_bandwidth = 0;
        for (i = 1; i <= device_number; i++) {
            scanf("%d", &manufacture);
            for (j = 0; j < manufacture; j++) {
                scanf("%d%d", &bandwidth[j], &price[j]);
                if (bandwidth[j] > max_bandwidth) {
                    max_bandwidth = bandwidth[j];
                }
            }
            if (i == 1) {
                dp[i - 1][max_bandwidth] = 0;
            }
            for (j = 1; j <= max_bandwidth; j++) {
                if (dp[i - 1][j] != -1) {
                    for (k = 0; k < manufacture; k++) {
                        min_number = min(j, bandwidth[k]);
                        if (dp[i][min_number] != -1) {
                            dp[i][min_number] = min(dp[i][min_number], dp[i - 1][j] + price[k]);
                        }
                        else {
                            dp[i][min_number] = dp[i - 1][j] + price[k];
                        }
                    }
                }
            }
        }
        ans = 0;
        for (j = 1; j <= max_bandwidth; j++) {
            if (dp[device_number][j] != -1) {
                temp = 1.0 * j / (dp[device_number][j]);
                if (temp > ans) {
                    ans = temp;
                }
            }
        }
        printf("%.3lf
", ans);
    }
}