題意：
一堆書，每本書都有厚度和高度，管理員試圖將這些書放到三層的書架上，每層都不能為空，求書架最小體積（書架深度顯然為所有書深度最大值，所以與排放方案無關，故取1）.
體積公式：
解題思想：
大概思路是DP，這個要先定下來
設v=(f(s1)+f(s2)+f(s3))*max{g(s1),g(s2),g(s3)}
其中g(s3)=SUM-g(s1)-g(s2)
f(s3)=max(h
i)
就說說，我們有4個決策變量
一個變量留給DP決策，另一個變量利用DP狀態設計來消除（這就需要對初始數據排序，保證決策過程中h
i<=h
p2,i屬于s2,p2為當前決策點）。
這個問題就轉化為在一個有序隊列上選擇兩個分割點p1,p2，h
p1<h
p2,使得max{hi,i屬于s1}<p1,max{hi,i屬于s2}<p2,并且s1,s2,s3均不為空
狀態可以設計為
F(i,t
1,t
2)
即考慮到第i個元素，s1的總厚度為t1,s2的總厚度為t2時p1所在元素的高度的最小值。
F（i,t1,t2)=min(F(i-1,t1,t2-data[i].t),data[i].h(當F(i-1,t1-data[i].t,t2)合法時),F(i-1,t1,t2))，顯然，三個轉移意義分別為將當前元素分配給s2、s1、s3
當F(i,t1,t2)由F(i-1,t1,t2-data[i].t)轉移過來的時候試圖更新全局最優解ans=min(ans,(data[i].h+F(i,t1,t2)+data[n-1].h)*t1*t2*(t
total-t1-t2))。注意，這里說F(i,t1,t2)由F(i-1,t1,t2-data[i].t)轉移過來指的是F(i-1,t1,t2-data[i].t)<=min(data[i].h(當F(i-1,t1-data[i].t,t2)合法時),F(i-1,t1,t2)),等于不能丟掉（原因？只有此時才能更新全局最優解）
代碼如下
1 Source Code
2
3 Problem: 3124 User: yzhw
4 Memory: 17744K Time: 2188MS
5 Language: G++ Result: Accepted
6 Source Code
7 # include <cstdio>
8 # include <utility>
9 # include <functional>
10 # include <cstring>
11 # include <vector>
12 # include <algorithm>
13 using namespace std;
14 # define M 2105
15 # define N 100
16 int dp[M][M],n,total,ans,sum[N];
17 pair<int,int> data[N];
18 bool cmp(const pair<int,int> &a,const pair<int,int> &b)
19 {
20 return a.first<b.first;
21 }
22
23 int main()
24 {
25 //freopen("bookcase.in","r",stdin);
26 int test;
27 scanf("%d",&test);
28 for(int t=1;t<=test;t++)
29 {
30 scanf("%d",&n);
31 total=0;
32 ans=0xfffffff;
33 for(int i=1;i<=n;i++)
34 {
35 scanf("%d%d",&data[i].first,&data[i].second);
36 total+=data[i].second;
37 }
38 sort(data+1,data+n+1,cmp);
39 sum[0]=0;
40 for(int i=1;i<=n;i++)
41 sum[i]=sum[i-1]+data[i].second;
42 memset(dp,-1,sizeof(dp));
43 dp[0][0]=0;
44 for(int i=1;i<=n;i++)
45 {
46 for(int j=sum[i-1];j>=0;j--)
47 for(int k=sum[i-1];k>=0;k--)
48 if(dp[j][k]!=-1)
49 {
50 if(dp[j+data[i].second][k]==-1||dp[j+data[i].second][k]>data[i].first)
51 dp[j+data[i].second][k]=data[i].first;
52 if(dp[j][k+data[i].second]==-1||dp[j][k+data[i].second]>=dp[j][k])
53 {
54 dp[j][k+data[i].second]=dp[j][k];
55 if(j&&j+k+data[i].second!=total)
56 ans=min(ans,(dp[j][k]+data[i].first+data[n].first)*max(j,max(k+data[i].second,total-j-k-data[i].second)));
57 }
58 }
59 }
60 printf("%d\n",ans);
61
62 }
63 return 0;
64
65