好题！这个题给我带来了很多思考
本来就不是很会做，看看了紫书才明白做法，这里权当自己复习一遍好了
首先给所有书规定一个顺序，把书按照书的高度由大到小排序，默认排序后第一本书放在第一层
定义状态dp[i][j][k]代表目前准备放第i+1本书，第二层的厚度为j，第三层的厚度为k时，第二层+第三层高度的最小值
于是就有3种状态的转移：
①把书放在第一层，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)
这是一个背包问题
我似乎对于“背包”的理解有点狭隘了
我似乎还没有理解动态规划更抽象的东西
本想说说感想，却啥也说不出来了
以下是原版本：
#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;} 以下是滚动数组的版本：#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;} 想一想在做最原始的背包问题的时候空间的优化，n个物品，容量为v的背包，空间复杂度从n*v→2*v→v，而且那个是单向更新，因此我断言这个滚动数组也可以省略掉，只不过这里是二维的情况，倘若省略掉的话，我本身也不想每一次循环都走一遍thick[n-1]，我还要做数组越界的判定，有点麻烦，还是算了吧。
新闻热点
疑难解答
