HDU 3669 Cross the Wall（斜率DP+预处理）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3669

题目大意：有n（n<=50000）个矩形，每个矩形都有高和宽，你可以在墙上最多挖k个洞使得可以通过，问你最小花费（所有挖的洞的h*w之和）是多少。

解题思路：先将所有矩形按宽从大到小，高从大到小，如果一个矩形宽和高都小于等于前面的矩形则肯定会被前面的矩形覆盖（完全放在前面的矩形里），那么这个矩形就可以删掉，因为不影响结果。

最后再倒序，使得宽从小到大，高从大到小，则状态转移方程为：dp[i][j]=min{dp[k][j-1]+a[k+1].h*a[i].w}(j-1<=k<i)。这样写复杂度为O（m*n^2）。发现dp[i][j]存在单调性，可以用斜率DP优化，使得复杂度降为O（m*n）。注意：记得特判当挖洞数增加但总花费不减少时，直接跳出DP，否则很大可能会超时。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int N=5e4+5;
 8 const int INF=0x3f3f3f3f;
 9 
10 int head,tail;
11 LL dp[N][105],q[N];
12 
13 struct node{
14     LL w,h;    
15     bool operator <(const node &b)const{
16         return w==b.w?h>b.h:w>b.w;
17     }
18 }a[N],tmp[N];
19 
20 LL getUP(int m,int k,int j){
21     return dp[k][j-1]-dp[m][j-1];
22 }
23 
24 LL getDOWN(int m,int k){
25     return a[m+1].h-a[k+1].h;
26 }
27 
28 LL getDP(int i,int j,int k){
29     return dp[k][j-1]+a[k+1].h*a[i].w;
30 }
31 
32 int main(){
33     int n,m;
34     while(scanf("%d%d",&n,&m)!=EOF){
35         for(int i=1;i<=n;i++){
36             scanf("%lld %lld",&tmp[i].w,&tmp[i].h);
37         }
38         sort(tmp+1,tmp+1+n);
39         int cnt=1;
40         a[1].h=tmp[1].h,a[1].w=tmp[1].w;
41         //删除会被完全覆盖的矩形 
42         for(int i=1;i<=n;i++){
43             if(a[cnt].h<tmp[i].h){
44                 cnt++;
45                 a[cnt].h=tmp[i].h;
46                 a[cnt].w=tmp[i].w;
47             }
48         }
49         reverse(a+1,a+1+cnt);
50         for(int i=1;i<=cnt;i++){
51             dp[i][1]=a[1].h*a[i].w;
52         }
53         LL ans=dp[cnt][1];
54         
55         for(int j=2;j<=m;j++){
56             head=tail=0;
57             q[tail++]=j-1;
58             dp[cnt][j]=INF;
59             for(int i=j;i<=cnt;i++){
60                 while(head+1<tail&&getUP(q[head],q[head+1],j)<=a[i].w*getDOWN(q[head],q[head+1])){
61                     head++;
62                 }
63                 dp[i][j]=getDP(i,j,q[head]);
64                 while(head+1<tail&&getUP(q[tail-1],i,j)*getDOWN(q[tail-2],q[tail-1])<=getUP(q[tail-2],q[tail-1],j)*getDOWN(q[tail-1],i)){
65                     tail--;
66                 }
67                 q[tail++]=i;
68             }
69             //加一句特判(从超时变成146ms),当挖洞数增多,花费未降低的时候,说明再增加挖洞数也不会降低花费,直接结束DP 
70             if(ans<=dp[cnt][j])
71                 break;
72             else
73                 ans=dp[cnt][j];
74         }
75         printf("%lld
",ans);
76     }
77     return 0;
78 }