[TIOJ 1522][UVa 12099] 球主的書櫃

作法：

這題之前在書上看過( 算法競賽入門經典第二版 )，那時就有寫過一次，再複習了一下。這題是用DP，首先我們可以把書的高度由大到小排序，並且可以假設最高的放在第一層。設 dp[ i ][ j ][ k ]代表目前放了 i 本書了，第二層和第三層的寬度分別是 j , k 的時候，高度的最小值。轉移的時候因為書的高度已經從大到小了，所以如果某一層有書了再放一本上去並不會改變高度，只有在 j = 0 且在第二層放書，或是在 k = 0 且在第三層放書的時候才會改變高度。另外 dp 陣列要用滾動的方式記錄記憶體才不會爆，只要開 dp[ 2 ][ 2101 ][ 2101 ] 就好了。但在DP的時候，還要注意到其實有很多狀態是無用的，因為總不可能 j + k + 第一本書的厚度 > 前 i 本書的厚度，所以超過的就可以不用算了，要多加這件事才不會TLE。

code :

#include<bits/stdc++.h>
#define INF 100000000
using namespace std;
const int maxn=70+10,maxm=2100+10 ;
 
struct P
{
    int h,w ;
    bool operator < (const P &rhs) const
    {
        return h>rhs.h ;
    }
}a[maxn] ;
 
int dp[2][maxm][maxm] ;
int sum[maxn] ;
 
inline void up(int &a,int b)
{
    if(b<a) a=b ;
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n ; scanf("%d",&n) ;
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].w) ;
        sort(a+1,a+n+1) ;
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].w ;
        dp[1][0][0]=a[1].h ;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j+a[1].w<=sum[i+1];j++)
                for(int k=0;k+j+a[1].w<=sum[i+1];k++)
                dp[(i+1)%2][j][k]=INF ;
 
            for(int j=0;j+a[1].w<=sum[i];j++)
                for(int k=0;k+j+a[1].w<=sum[i];k++)
                if(dp[i%2][j][k]!=INF)
            {
                int val=dp[i%2][j][k] ;
                up(dp[(i+1)%2][j][k],val) ;
                int add1= j==0?a[i+1].h:0 ;
                up(dp[(i+1)%2][j+a[i+1].w][k],val+add1) ;
                int add2= k==0?a[i+1].h:0 ;
                up(dp[(i+1)%2][j][k+a[i+1].w],val+add2) ;
            }
        }
 
        int ans=INF ;
        for(int j=1;j+a[1].w<=sum[n];j++)
            for(int k=1;j+k+a[1].w<=sum[n];k++)
            if(dp[n%2][j][k]!=INF)
        {
            int M=max(sum[n]-j-k,max(j,k)) ;
            up(ans,M*dp[n%2][j][k]) ;
        }
        printf("%d\n",ans) ;
    }
}