好題！這個題給我?guī)砹撕芏嗨伎?/p>

        本來就不是很會做，看看了紫書才明白做法，這里權(quán)當自己復習一遍好了

        首先給所有書規(guī)定一個順序，把書按照書的高度由大到小排序，默認排序后第一本書放在第一層

        定義狀態(tài)dp[i][j][k]代表目前準備放第i+1本書，第二層的厚度為j，第三層的厚度為k時，第二層+第三層高度的最小值

        于是就有3種狀態(tài)的轉(zhuǎn)移：

            ①把書放在第一層，dp[i+1][j][k]=dp[i][j][k]

            ②把書放在第二層，dp[i+1][j+book[i+1].second][k]=dp[i][j][k]+(j==0?book[i+1].first:0);j為0代表第二層沒有放書，因此要+上高度，.first代表高度,.second代表寬度

            ③把書放在第三層，類似。dp[i+1][j][k+book[i+1].second]=dp[i][j][k]+(k==0?book[i+1].first:0)

        這是一個背包問題

        我似乎對于“背包”的理解有點狹隘了

        我似乎還沒有理解動態(tài)規(guī)劃更抽象的東西

        本想說說感想，卻啥也說不出來了

        以下是原版本：

#include <iostream>#include <cstring>#include <algorithm>using namespace std;using pa=pair<int,int>;int times,n,dp[75][2105][2105],thick[75],ans=0x3f3f3f3f;pa book[75];inline void update(int& newstate,int k){    if(newstate<0||newstate>k)        newstate=k;}int main(){    ios_base::sync_with_stdio(false);    cin>>times;    while(times--){        cin>>n;        for(int i=0;i<n;++i)            cin>>book[i].first>>book[i].second;        sort(book,book+n,[](const pa& a,const pa& b){return a.first>b.first||a.first==b.first&&a.second>b.second;});        memset(dp,-1,sizeof dp);        thick[0]=book[0].second;        for(int i=1;i<n;++i)            thick[i]=thick[i-1]+book[i].second;        dp[0][0][0]=0;        for(int i=0;i<n-1;++i)        for(int j=0;j<=thick[i+1]-thick[0];++j)        for(int k=0;k<=thick[i+1]-thick[0]-j;++k)        if(dp[i][j][k]>=0){            update(dp[i+1][j][k],dp[i][j][k]);            update(dp[i+1][j+book[i+1].second][k],dp[i][j][k]+(j==0?book[i+1].first:0));            update(dp[i+1][j][k+book[i+1].second],dp[i][j][k]+(k==0?book[i+1].first:0));        }        for(int i=1;i<=thick[n-1]-thick[0];++i)        for(int j=1;j<=thick[n-1]-thick[0]-i;++j)        if(dp[n-1][i][j]>=0)            ans=min(ans,max(max(j,i),thick[n-1]-i-j)*(book[0].first+dp[n-1][i][j]));        cout<<ans<<endl;        ans=0x3f3f3f3f;    }    return 0;}
        以下是滾動數(shù)組的版本：
#include <iostream>#include <cstring>#include <algorithm>using namespace std;using pa=pair<int,int>;int times,n,dp[2][2105][2105],t,thick[75],ans=0x3f3f3f3f;pa book[75];inline void update(int& newstate,int k){    if(newstate<0||newstate>k)        newstate=k;}int main(){    ios_base::sync_with_stdio(false);    cin>>times;    while(times--){        cin>>n;        for(int i=0;i<n;++i)            cin>>book[i].first>>book[i].second;        sort(book,book+n,[](const pa& a,const pa& b){return a.first>b.first||a.first==b.first&&a.second>b.second;});        thick[0]=book[0].second;        for(int i=1;i<n;++i)            thick[i]=thick[i-1]+book[i].second;        dp[t][0][0]=0;        for(int i=0;i<n-1;++i){            //memset(dp[t^1],-1,sizeof dp[t^1]);            t^=1;            for(int j=0;j<=thick[i+1];++j)            for(int k=0;k<=thick[i+1]-j;++k)                dp[t][j][k]=-1;            t^=1;            for(int j=0;j<=thick[i]-thick[0];++j)            for(int k=0;k<=thick[i]-thick[0]-j;++k)            if(dp[t][j][k]>=0){                update(dp[t^1][j][k],dp[t][j][k]);                update(dp[t^1][j+book[i+1].second][k],dp[t][j][k]+(j==0?book[i+1].first:0));                update(dp[t^1][j][k+book[i+1].second],dp[t][j][k]+(k==0?book[i+1].first:0));            }            t^=1;        }        for(int i=1;i<=thick[n-1]-thick[0];++i)        for(int j=1;j<=thick[n-1]-thick[0]-i;++j)        if(dp[t][i][j]>=0)            ans=min(ans,max(max(j,i),thick[n-1]-i-j)*(book[0].first+dp[t][i][j]));        cout<<ans<<endl;        ans=0x3f3f3f3f;    }    return 0;}
        想一想在做最原始的背包問題的時候空間的優(yōu)化，n個物品，容量為v的背包，空間復雜度從n*v→2*v→v，而且那個是單向更新，因此我斷言這個滾動數(shù)組也可以省略掉，只不過這里是二維的情況，倘若省略掉的話，我本身也不想每一次循環(huán)都走一遍thick[n-1]，我還要做數(shù)組越界的判定，有點麻煩，還是算了吧。