Online Judge：Luogu-P2160
Label：思维题，Dp，空间优化
题面：
题目描述
给(N)本书，每本书有高度(Hi),厚度(Ti)。要摆在一个三层的书架上。
书架的宽是每层书厚度和的最大值。书架的高度是每层最高书的高度之和。
求如何放书，使得书架的面积最小。
输入
第一行一个整数(n)，表示书本的个数。
接下来(n)行，每行2个整数，表示每本书的高度和厚度。
输出
输出一个整数，表示书架的最小面积。
样例
Input
4
220 29
195 20
200 9
180 30
6
256 20
255 30
254 15
253 20
252 15
251 95 2
25 25 32 32 25
5 1
25 26 25 26 25
0 0
Output
18000
29796
提示
每层书架都必须有书。
样例1：第一本书在第一层，第二本、第三本书在第二层，第四本书在第三层！
高度是220+200+180=600，宽度为max(29,29,30)=30，总面积18000。
对于100%的数据，n的范围([3,70]),h[i]的范围([150,300]),t[i]的范围([1,30])。
题解
首先注意到一点，高度最高的那本书，不论我们把它放在1、2、3层，它都会成为它那一层的最高。所以不妨先确定下这本书，把这本高度最高的书放在第一层，那么第一层在高度上对答案的贡献就可以确定为这个最大高度了。
如何去安排上面两层使得面积最小呢。现在存在两维——高度和宽度，我们尝试利用Dp消掉其中一个来简化问题。
1.定义
定义状态(dp[i][p1][p2])表示，已经摆放好了前(i)本书（注意到摆书的顺序对答案是没有影响的），第二层剩余的宽度为(p1)，第三层剩余的宽度为(p2)，此时二三两层加起来的总高度最小能为多少。
2.转移
等等，这样该如何转移呢？按常规转移思路来说应该还得记录下其中一层的高度，不然我现在放的书比之前放在这一层的那本书高度要大时，理应更新这一层在高度上对答案的贡献才对，但我此刻却不知道之前这一层的高度是多少。
解决方案不难想到，我们可以直接从大到小排序高度，那么假如这本书是当前层所放的第一本书，那么这一层在高度上对答案的贡献就确定了(后面不会再有书比现在的书高了)。
这样我们就可以利用填表进行转移勒：
初态：(dp[i][p1][p2]=)INF，$dp[1][0][0]=$1。
inline void Do(int &x,int y){if(x>y)x=y;}
枚举i,j,k{
if(a[i].w<j)Do(dp[j][k],dp[j-a[i].w][k]);
else if(j==a[i].w)Do(dp[j][k],dp[0][k]+a[i].h);//i是第二层放的第一本书
if(a[i].w<k)Do(dp[j][k],dp[j][k-a[i].w]);
else if(k==a[i].w)Do(dp[j][k],dp[j][0]+a[i].h);//i是第三层放的第一本书
}
终态：枚举(p1,p2)，(ans=max(ans,H*W))，其中(H=dp[n][p1][p2]+Maxheight)，(W=max(p1,max(p2,Lim-p1-p2))，(Lim)表示所有书的宽度之和。
3.空间优化
还有一个问题就是空间显然会炸。
第一种解决方案：根据上面的转移顺序可以知道，对于第(i)本书，只会用到第(i-1)本书的状态，所以显然可以把第一维给滚动了。
第二种解决方案：但也可以直接去掉这一维而无需滚动。但是转移顺序得稍微调整一下，我们上面枚举的(j,k)得从大到小枚举，这和01背包倒着循环是一个道理。
4.一点时间上的小优化
前面枚举(j,k)的上限不必为(Lim)（所有书本的宽度总和），可以用前缀和来代替，从而省去很多无用的枚举。
综上此做法时间复杂度为(O(N*Lim*Lim))，其中(N<=70,Lim<=2100)。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF=1890000;
inline int read(){}
int n,m,Lim;
int dp[2200][2200],sum[75];
struct node{int h,w;}a[75];
inline bool cmp(node x,node y){return x.h>y.h;}
inline void Do(int &x,int y){if(x>y)x=y;}
int main(){
n=read();
for(register int i=1;i<=n;i++){
a[i].h=read(),a[i].w=read();
Lim+=a[i].w;
}
sort(a+1,a+n+1,cmp);
for(register int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].w;
for(register int i=0;i<=Lim;i++)for(register int j=0;j<=Lim;j++)dp[i][j]=INF;
dp[0][0]=0;
for(register int i=2;i<=n;i++){
for(register int j=sum[i];j>=0;j--)for(register int k=sum[i];k>=0;k--){
if(a[i].w<j)Do(dp[j][k],dp[j-a[i].w][k]);
else if(j==a[i].w)Do(dp[j][k],dp[0][k]+a[i].h);
if(a[i].w<k)Do(dp[j][k],dp[j][k-a[i].w]);
else if(k==a[i].w)Do(dp[j][k],dp[j][0]+a[i].h);
}
}
int ans=INF;
for(register int i=1;i<=Lim;i++)for(register int j=1;j<=Lim;j++){
if(dp[i][j]==INF)continue;
int H=dp[i][j]+a[1].h,W=max(Lim-i-j,max(i,j));
Do(ans,H*W);
}
printf("%d
",ans);
}
END
当题目中存在多种决定因素时，可以考虑使用Dp求最值来消去其中的一维或多维。
通过排序等方法来改变转移顺序，从而简化问题。