【POJ】【1821】Fence

DP/单调队列优化

　　题意：k个人粉刷总长为n的墙壁（或者说栅栏？），每个人有一个必刷点s[i]（这个人也可以一点也不刷，如果刷就必须刷这个点），最大粉刷长度l[i]（必须是连续粉刷一段），和粉刷一格的报酬p[i]，每格不能重复粉刷，求最大报酬总和。

　　唉……orz了一下proverbs，表示列dp方程是我的硬伤啊……

Tricks：

　　转移！这个转移的边界没搞清……从$ s[i]-l[i] $到$ s[i]-1 $都是可行的，转移到的状态是$s[i]$到$s[i]+l[i]-1$

　　排序！T_T很明显为了避免后效性是一定要先DP完$s$靠前的人的……sigh

 1 Source Code
 2 Problem: 1821        User: sdfzyhy
 3 Memory: 7036K        Time: 47MS
 4 Language: G++        Result: Accepted
 5 
 6     Source Code
 7 
 8     //POJ 1821
 9     #include<cmath>
10     #include<vector>
11     #include<cstdio>
12     #include<cstring>
13     #include<cstdlib>
14     #include<iostream>
15     #include<algorithm>
16     #define rep(i,n) for(int i=0;i<n;++i)
17     #define F(i,j,n) for(int i=j;i<=n;++i)
18     #define D(i,j,n) for(int i=j;i>=n;--i)
19     #define pb push_back
20     using namespace std;
21     int getint(){
22         int v=0,sign=1; char ch=getchar();
23         while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
24         while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
25         return v*=sign;
26     }
27     const int N=16010,M=110,INF=~0u>>2;
28     typedef long long LL;
29     /******************tamplate*********************/
30 
31     int dp[M][N],n,k;
32     struct node{
33         int x,v;
34     }q[N];
35     struct ques{
36         int l,p,s;
37         bool operator <(const ques&b)const{
38             return s<b.s;
39         }
40     }a[M];
41     int main(){
42     #ifndef ONLINE_JUDGE
43         freopen("1821.in","r",stdin);
44         freopen("1821.out","w",stdout);
45     #endif
46         n=getint(); k=getint();
47         F(i,1,k){ a[i].l=getint(); a[i].p=getint(); a[i].s=getint();}
48         sort(a+1,a+k+1);
49         int l,p,s,st,ed;
50         F(i,1,k){
51             l=a[i].l; p=a[i].p; s=a[i].s;
52             st=ed=0;
53             F(j,0,n){
54                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
55                 if (j>=s-l && j<s){
56                     while(st<ed && q[ed-1].v<dp[i-1][j]-p*j) ed--;
57                     q[ed++]=(node){j,dp[i-1][j]-p*j};
58                 }
59                 if (j>=s && j<=s+l-1){
60                     while(st<ed && q[st].x<j-l) st++;
61                     dp[i][j]=max(dp[i][j],q[st].v+p*j);
62                 }
63             }
64         }
65         printf("%d
",dp[k][n]);
66         return 0;
67     }

View Code