POJ1821Fence

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

POJ1821Fence
POJ1821Fence
 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\n",dp[k][n]);
66         return 0;
67     }
View Code

 

更多相关文章
  • POJ 1821 Fence
    Fence Time Limit: 1ms Memory Limit: 30KB This
  • 题目连接 http://poj.org/problem?id=3253   Fence Repair Description Farmer John wants to repair a small length of the fence around the pasture. He measures
  • 题目链接:http://poj.org/problem?id=3253 思路分析:题目与哈夫曼编码原理相同,使用优先队列与贪心思想:读入数据在优先队列中,弹出两个数计算它们的和,再压入队列中:   代码如下:  #include <iostream> #include <queue ...
  • 思路:每次枚举每个工人的右边界j,维护最优的左边界k.那么dp[j]=max(dp[j],dp[k]+(j-k)*w[i].p): 对于每个工人的初值k=w[i].s-1; 令x=j-w[i].l,如果(k-x)*w[i].p>dp[k]-dp[x],则k=x. #include<set ...
  •   列表一:经典题目题号:容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1191,1208, 1276, 1322, 1414, 1456, 1458,  1609, 1644, 1664, 1690, 1
  •   2014年4月份日常记录表(2014.4.1—4.30,30天) 日期 周次 天数 编程 日记 阅读 英语 备注 2014.4.1 周二 第1天 完成 完成 完成 完成 <ACM-ICPC培训资料汇编(7)计算几何分册>基本几何运算 <数据结构教程>课后题 2014.4. ...
  • poj 1037 A decorative fence
    题目链接:http://poj.org/problem?id=1037 Descripti
  • Fence Repair Time Limit: 2MS Memory Limit: 65536K Total Submissions: 32424 Accepted: 10417 Description Farmer John wants to repair a small length of t
一周排行