当前位置: 首页 > news >正文

P1545 [USACO04DEC] Dividing the Path G 题解

P1545 [USACO04DEC] Dividing the Path G 题解

最近开始快刷蓝紫黑了,做完会写题解交上来。

题目传送门

题意

一条长为 \(L(1 \le L \le 10^6 , 2 | L)\) 的线段上,给出 \(N(1 \le N \le 10^3)\) 个可能相交的子段 \([S_i,E_i]\),现要求用若干个长度在 \([2a,2b]\) 中且为偶数的小线段覆盖整个大线段。

要求:

  • 整个大线段都要被覆盖。
  • 用来覆盖的小线段不相交。
  • 每个子段能且仅能被唯一一个小线段覆盖。
  • 小线段的范围不能超出大线段。

求出最少用来覆盖的小线段的个数。

分析

这道题暴力 \(O(L^2)\) 是好写的,设 \(dp_i\) 表示覆盖 \([0,i]\) 所需的小线段个数(显然 \(i\) 必须为某个子段的端点),答案明显为 \(dp_L\) ,边界也是显而易见的:\(dp_0=0\)

转移有如下式子:

\[dp_i=\min_{j=i-2b,2|j}^{i-2a}(dp_j+1) \]

然后交了一发就过了。

虽然数据较水,但我们仍需要考虑正解。

转移方程中,取最小值里的 \(+1\) 可以提出来,所以我们实际上是在求 \(\min dp_j\)

我们其实会很容易地发现这其实就是在一段区间里取最小值。

每次转移完当前点的值,我们都会把它当作下次转移时的区间里的一部分。

提炼一下:区间取 \(\min\),单点修改。

线段树可以很方便的处理掉,复杂度 \(O(L\log L)\)

AC Code
#include<bits/stdc++.h>
#define int long long 
#define rep(I,A,B) for(int I=(A);I<=(B);++I)
#define per(I,A,B) for(int I=(A);I>=(B);--I)
#define el puts("")
#define Yuki return 
#define daisuki 0
#define debug puts("SKIRK")
#define none 'N'
#define ed '\n'
#define pc putchar
using namespace std;
using pii=pair<int,int>;
//fastIO start
template<typename T>
void read(T &x){x=0;bool f=0;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=1;for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);if(f)x=-x;
}
template<typename T,typename ...Args>
void read(T &x,Args &...args){read(x),read(args...);
}
template<typename T>
void write(T x,char ch=' '){if(x<0)putchar('-'),x=-x;static short st[70],tp;do st[++tp]=x%10,x/=10;while(x);while(tp)putchar(st[tp--]|48);if(ch!=none)putchar(ch);
}
void writes(string str){rep(i,0,str.size()-1)putchar(str[i]);
}
void writec(char chs){putchar(chs);
}
//fastIO end
const int N=1e3+5;
const int L=1e6+5;
const int inf=0x3f3f3f3f;
struct edge{int s,e;
}p[N];
int n,l,a,b;
bool vis[L];
int dp[L];
struct node{int l,r,mn;
}tr[L<<2];
void build(int p,int l,int r){tr[p].l=l;tr[p].r=r;tr[p].mn=inf;if(l==r)return ;int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
int query(int p,int L,int R){int l=tr[p].l;int r=tr[p].r;if(r<L||l>R)return inf;if(L<=l&&r<=R)return tr[p].mn;return min(query(p<<1,L,R),query(p<<1|1,L,R));
}
void modify(int p,int L,int v){int l=tr[p].l;int r=tr[p].r;if(r<L||l>L)return ;if(l==r)return tr[p].mn=v,void();modify(p<<1,L,v);modify(p<<1|1,L,v);tr[p].mn=min(tr[p<<1].mn,tr[p<<1|1].mn);
}
signed main(){read(n,l,a,b);rep(i,1,n){read(p[i].s,p[i].e);rep(j,p[i].s+1,p[i].e-1)vis[j]=1;}memset(dp,0x3f,sizeof(dp));dp[0]=0;build(1,0,l);modify(1,0,0);for(int i=2;i<=l;i+=2){if(vis[i])continue;dp[i]=query(1,max(i-2*b,0ll),i-2*a)+1;modify(1,i,dp[i]);// rep(j,a,b){      //暴力转移//   int k=i-j*2;//   if(k<0)continue;//   Min(dp[i],dp[k]+1);// }}if(dp[l]>=inf)dp[l]=-1;write(dp[l]);Yuki daisuki;//Yuki真的是太可爱了捏
}  
//by oSomiwww
http://www.hskmm.com/?act=detail&tid=26697

相关文章:

  • 视频采集程序
  • java作业2
  • 关于PPT的课后作业
  • RK 系列 GPU 驱动检查方法
  • 咕乡
  • Linux随记(十八) - 详解
  • week2课后作业
  • Java 语言程序设计(第二讲 方法)动手动脑与课后实验问题整理文档 - 20243867孙堃2405
  • 算法第一章
  • mac打开app提示文件损坏解决方案
  • QBXT2025S刷题 Day7题
  • 无需重新训练即可更新语音识别词汇
  • 深入解析:vscode中无法使用npm node
  • 第一次算法作业
  • AI元人文:新的评价与启示
  • Ai元人文:岐金兰回应
  • Why is English commonly used in scientific literature?
  • 第二次课程
  • 考研系列—操作系统:冲刺笔记(1-3章) - 指南
  • 智能照明系统厂家最新推荐榜:智慧光控与节能方案口碑之选
  • 2025工业网线优质厂家最新推荐榜:品质卓越与技术领先之选
  • 上海殡葬一条龙服务最新推荐:专业关怀与人性化服务口碑之选
  • 中空扳手实力厂家最新推荐榜:专业制造与耐用品质深度解析
  • 驾驭“人造太阳”:用 AI 来解锁聚变核能
  • sg.Multiline 和 sg.Output 有什么区别?怎么看起来一样?
  • 中科微GNSS卫星定位产品
  • 算法设计与分析第一章作业
  • Syncfusion重构Essential Studio套件,为开发者提供更灵活选择
  • vmware workstation17pro安装vmtools
  • 2025 年逸发粘接认证推荐:依托德系标准与全链条服务,打造粘接及复材技术解决方案优质选择