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

 

更多相关文章
一周排行
  • rpm包一般都有默认的安装路径,如何你要更改默认路径,有没有辦法呢?当然有.我们来看下面的例子. 比如在安装JDK (Java Development Kit)或JRE (Java Runtime Environme ...
  • 华夫人:我们Notebook是由MathWork公司在MATLAB5.0中开始增加,实现MATLAB和Word的连接. 唐伯虎:哼!我们ExcelLink是在Windows环境下实现的Excel与Matlab连接. ...
  • 环境要求: 首先需要准备好一台Citrix XenApp Server 6.5的服务器 本文档以windows随机的应用程序notepad为例. 注意:本文档的发布应用程序的方法,仅限Citrix XenApp 6.
  • Android frameworkAndroidManagerService初始化流程
    源码基于Android 4.4.   system_server的初始化 system_s ...
  • 简介 如何在php中方便地解析html代码,估计是每个phper都会遇到的问题.用phpQuery就可以让php处理html代码像jQuery一样方便. 项目地址:https://code.google.com/p/
  • 随着Linux的发展,很多人开始学习Linux系统,你了解Linux系统么?你是Linux系统的应用者么?本文为你详细介绍Linux安装Eclipse,为你在学习Linux安装Eclipse时起一定的作用.以下是Li ...
  • 码如下面: #define OTL_BIGINT long long #define OTL_STR_TO_BIGINT(str,n) \ { \ n=atoll(str); \ } #define OTL_BIGI
  • 2015年马上过半年了.终于第一个大版出来了. What's New in 15.1.2 (VCL Product Line)   New Major Features in 15.1 What's New in V ...
  • Zynq學習筆記(1)
    做硬件的第一个实例,一般当然是LED点灯啦~   硬件:ZedBoard 软件:ISE 1
  • 1 安装 解压jad.zip文件到任何的目录.将会创建两个文件,一个是jad.exe另一个是readme文 件,不需要任何别安装2 如何使用jad 如果我们有一个单独的java文件example1.class. &g ...