uvalive3637(DP)

제목: n권의 책을 제시하고 책의 높이와 너비를 각각 제시한다. 3층 책꽂이를 세워야 한다. 책꽂이의 높이는 3층 책꽂이의 높이와 책꽂이의 너비는 3층 중 가장 넓은 책꽂이의 너비이다. 가장 작은 책꽂이의 면적은 얼마냐고 묻는다.
사고방식: (세 층이 있으면 두 층만 고려하면 되고 세 번째 층은 자동으로 확정된다) DP.책의 높이에 따라 큰 것부터 작은 것까지 순서를 정하다.예상하기 어려운 DP.dp[i][j]를 설정하면 2층 너비가 i 3층 너비가 j일 때의 최소 높이를 나타낸다.순서가 이미 큰 것에서 작은 것까지 정렬되었기 때문이다.그래서 책꽂이에 넣은 첫 번째 책은 틀림없이 이 층에서 가장 높은 것이다.그렇다면 이 책이 이 층의 첫 번째 책인지 아닌지를 판단하기만 하면 원래의 기초 위에서 높이를 더해야 한다. 그렇지 않으면 너비를 더한 후의 높이가 원래의 높이와 같다.
코드:

#include <iostream>
using namespace std;
#include <cstring>
#include <stdio.h>
#include <algorithm>
const int maxn = 2500;
const int INF = 0x3f3f3f3f;

struct book {
    int h,w;
}p[100];

int dp[maxn][maxn],n;

bool cmp(book a,book b) {
    return a.h > b.h;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int tot = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d%d",&p[i].h,&p[i].w);
            tot += p[i].w;
        }
        sort(p,p + n,cmp);
        for(int i = 0; i <= tot; i++)
            for(int j = 0; j <= tot; j++)
                dp[i][j] = INF;
        dp[0][0] = 0;
        for(int k = 1; k < n; k++) {
            for(int i = tot; i >= 0; i--) {
                for(int j = tot; j >= 0; j--) {
                    if(dp[i][j] != INF) {
                        if(i == 0)
                            dp[i + p[k].w][j] = min(dp[i + p[k].w][j],dp[i][j] + p[k].h);
                        else
                            dp[i + p[k].w][j] = min(dp[i + p[k].w][j],dp[i][j]);
                        if(j == 0)
                            dp[i][j + p[k].w] = min(dp[i][j + p[k].w],dp[i][j] + p[k].h);
                        else
                            dp[i][j + p[k].w] = min(dp[i][j + p[k].w],dp[i][j]);
                    }
                }
            }
        }
        int ans = INF;
        for(int i = 1; i <= tot; i++) {
            for(int j = 1; j <= tot; j++) {
            if(dp[i][j] != INF) {
                int w = max(i,j);
                w = max(w,tot - i - j);
                ans = min(ans,(dp[i][j] + p[0].h) * w);
            }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}