UVALive 3637 The Bookcase

제목 대의: n(3<=n<=70)권의 책이 있습니다. 지금은 책꽂이가 하나 있습니다. 책꽂이는 3층이 있습니다. n권의 책을 책꽂이에 놓아야 합니다. 층마다 비워서는 안 됩니다. 책마다 높이와 너비, 하이와티가 있습니다. 이것을 가장 작게 하려면 이 최소치를 물어보세요.
사고방식: d[i][i][j]를 설정하면 전 i본, 2층의 t와 j, 3층의 t와 k의 2, 3층의 최대 높이의 합을 나타낸다.우리는 먼저 모든 책을 높이에 따라 큰 것부터 작은 것까지 순서를 정하면 한 권씩 들어간다. 이 층이 비어 있지 않으면 이 책의 높이는 d치에 영향을 주지 않는다. 즉, 각 층의 높이는 이 층이 들어온 첫 번째 책에 달려 있다. 한 권당 세 가지 선택만 있고 두 번째 층이나 두 번째 층, 또는 세 번째 층에 놓으면 d[i][j]]=min(d[i-1]j][k-book].t]+book[i].h,[i]j]]][i]]]]]]]][i]]]]]]][i]]]]][i]]]]]]]]]]][i]]]][i][i]]]]][i]]]]]]]]]]k == book[i].t;d[ i ][ j ][ k] = min(d[i - 1][ j - book[i].t][ k ] + book[i].h,d[ i- 1 ][ j ][ k ]) ,j == book[i].t;d[ i ][ j ][ k ] = min(d[ i - 1][ j ][ k ] ,d[ i - 1 ][ j - book[i].t ][ k ],d[ i - 1 ][ j ][ k - book[i].t ]),j > book[i].t,k > book[i].t .2, 3층의 t와 t를 알게 되면 1층은 s-i-j이고 관건은 1층의 h에 있다.여기서 우리는 높이가 가장 큰 책을 1층, 즉 정렬된 책[1]에 놓고 DP를 할 때 i=2부터 시작하기 때문에 정답은 min((d[n]i][j]+책[1].h)*max(i, j, s-i-j))이다.공간 문제 때문에, 여기에는 스크롤 수조로 공간을 최적화해야 한다.
이 문제의 DP는 정말 보고 싶지 않다. 원래는 세 가지 차원만 있으면 된다. 작은 것부터 큰 것까지 순서를 정하고 그 다음에 높이에 영향을 주지 않는다. 세 번째 t와 뺄 수 있다. 그리고 DP는 2부터 첫 번째 책을 1층에 놓는다. 이런 것들은 정말 생각지도 못했다. 계속 연습하자...(>_<)~~~~
코드는 다음과 같습니다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;

#define MP make_pair

const int INF = 0x0fffffff ;

const int MAXN = 77;

pii book[MAXN];

int cmp(pii a,pii b)
{
    return a.first > b.first ;
}

int d[2222][2222];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int sum_w = 0;
        for(int i = 1;i<=n;i++)
        {
        	int a,b;
         	scanf("%d%d",&a,&b);
          	book[i] = MP(a,b);
          	sum_w += b;
        }
        sort(book + 1,book + 1 + n ,cmp);
        for(int i = 0;i<=sum_w;i++)
            for(int j = 0;j<=sum_w;j++)
                d[i][j] = INF;
        d[0][0] = 0;
        for(int i = 2;i<=n;i++)
        {
        	for(int j = sum_w;j>=0;j--)
        		for(int k = sum_w;k>=0;k--)
        		{
           			if(book[i].second == j) d[j][k] = min(d[j][k] , d[0][k] + book[i].first);
           			if(book[i].second == k) d[j][k] = min(d[j][k] , d[j][0] + book[i].first);
              		if(j > book[i].second) d[j][k] = min(d[j][k],d[j - book[i].second][k]);
              		if(k > book[i].second) d[j][k] = min(d[j][k],d[j][k - book[i].second]);
                 }
		}
  		int ans = INF;
    	for(int i = 1;i<sum_w;i++)
     		for(int j = 1;j<sum_w;j++)
       		{
         		if(d[i][j] >= INF) continue;
           		int w = max(max(i,j),sum_w - i - j);
             	int h = d[i][j] + book[1].first;
              	ans = min(ans,w*h);
           	}
		printf("%d
",ans);
    }
    return 0;
}