2018.09.12 poj2376Cleaning Shifts(线段树+简单dp)
2024-10-12 17:31:44
传送门
貌似贪心能过啊%%%。
本蒟蒻写的线段树优化dp。
式子很好推啊。
f[i]表示覆盖1~i所需的最小代价。
那么显然对于一个区间[li,ri]" role="presentation" style="position: relative;">[li,ri][li,ri]
有f[ri]=min(f[j])+1,li−1≤j≤ri" role="presentation" style="position: relative;">f[ri]=min(f[j])+1,li−1≤j≤rif[ri]=min(f[j])+1,li−1≤j≤ri
这样推出f[t]的值就行了。
请别忘了给区间排序
代码:
#include<iostream>
#include<cctype>
#include<cstdio>
#include<algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 1000005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,t,f[N];
struct Node{int l,r,mn;}T[N<<2];
struct Q{int l,r;}q[25005];
inline int min(int a,int b){return a<b?a:b;}
inline void pushup(int p){T[p].mn=min(T[lc].mn,T[rc].mn);}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].mn=0x3f3f3f3f;
if(l==r){if(l==0)T[p].mn=0;return;}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int k,int v){
if(T[p].l==T[p].r){T[p].mn=v;return;}
if(k<=mid)update(lc,k,v);
else update(rc,k,v);
pushup(p);
}
inline int query(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return 0x3f3f3f3f;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].mn;
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return min(query(lc,ql,mid),query(rc,mid+1,qr));
}
inline bool cmp(Q a,Q b){return a.r==b.r?a.l<b.l:a.r<b.r;}
int main(){
n=read(),t=read();
build(1,0,t);
for(int i=1;i<=n;++i)q[i].l=read(),q[i].r=read();
for(int i=1;i<=t;++i)f[i]=0x3f3f3f3f;
sort(q+1,q+n+1,cmp);
for(int i=1;i<=n;++i){
if(q[i].l<1)q[i].l=1;
if(q[i].r>t)q[i].r=t;
int tmp=query(1,q[i].l-1,q[i].r);
if(tmp+1<f[q[i].r])f[q[i].r]=tmp+1,update(1,q[i].r,(f[q[i].r]=tmp+1));
}
cout<<(f[t]==0x3f3f3f3f?-1:f[t]);
return 0;
}
最新文章
- python 运行时报错误SyntaxError: Non-ASCII character &#39;\xe5&#39; in file 1.py on line 2
- [apache]用shell分析网站的访问情况
- Oracle监听器—动态注册
- VSPackge插件系列:简单文本编辑器的实现
- Extjs4.2.1学习笔记[更新]
- jQuery API中文文档
- Hortonworks HDP Sandbox定制(配置)开机启动服务(组件)
- 快速开发 HTML5 交互式地铁线路图
- 下载Android源代码编译错误总结
- asp.net Core 中AuthorizationHandler 实现自定义授权
- 记一次CPU飙升BUG
- JVM中垃圾收集算法总结
- jstack 使用一例
- 2019.3.22 Week 11 : ZigBee power test and field test
- Android应用的基本原理
- git push失败
- bzoj4399 魔法少女LJJ 线段树合并
- BZOJ4978: [Lydsy1708月赛]泛化物品(乱搞)
- background-position为什么会出现负值?
- HTML5关于上传API的一些使用(下)