题目链接:http://acm.uestc.edu.cn/problem.php?pid=1558
题目大意:给定n个区间[begi,endi],表示能从begi转换到endi,每个区间都有一个权值ti,现在要从1转换到大等于m的一个状态,问最少的权值,如果没办法到达那个状态,输出-1。n<=10万。
解题思路:线段树优化DP。如果n很小,那么这题有好多解法,用最短路(如果两个区间相连就添加一条边)或者朴素的N^2的DP(状态转移方程dp[endi] = min(dp[k]) + ti ,begi<=k<=endi)。这题n很大但仍然考虑用DP,因为每次状态转移都要用到前面某个区间的最小值,而这个查询操作用线段树就能以logn的复杂度完成,还有更新操作,只要更新endi这个点就可以,这就是最简单的单点更新线段树。为什么更新的时候只要更新一点就可以呢?为了达到这种效果我们按照区间的endi对所有区间排序,这样当前的endi肯定比之前的大,查询的时候是查询整个区间,那么endi那个点所在的最小权值就能反应整个区间的情况。
测试数据:3
3 10
5 1 3
8 2 5
10 9 2
4 5
2 1 1
3 2 1
4 3 1
8 4 1
5 9
5 1 1
10 4 10
8 1 10
11 6 1
7 3 8
代码:#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 210000
#define int64 long long
#define INF (0xffffffffffff)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct node {
int beg,end,time;
}arr[MAX];
int64 ans,Min[MAX*3];
int n,m,tot,cnt,dis[MAX*3];
inline int64 min(int64 a,int64 b) {
return a<b?a:b;
}
int Binary(int x) {
int low = 1,high = tot,mid;
while (low <= high) {
mid = (low + high) >> 1;
if (dis[mid] == x) return mid;
else if (dis[mid] < x) low = mid + 1;
else high = mid - 1;
}
}
void DisCret() {
//离散化
int i;
dis[cnt++] = 1,dis[cnt++] = m;
sort(dis+1,dis+cnt);
for (i = 2; i < cnt; ++i)
if (dis[i] != dis[i-1]) dis[++tot] = dis[i];
for (i = 1; i <= n; ++i) {
arr[i].beg = Binary(arr[i].beg);
arr[i].end = Binary(arr[i].end);
}
}
int cmp(node a,node b){
if (a.end != b.end) return a.end < b.end;
else return a.beg < b.beg;
}
void Push_Up(int rt) {
Min[rt] = Min[rt<<1]<Min[rt<<1|1]?Min[rt<<1]:Min[rt<<1|1];
}
void Build_Tree(int l,int r,int rt) {
if (l == r) {
Min[rt] = l == 1 ? 0 : INF;
return;
}
int m = (l + r) >> 1;
Build_Tree(lson);
Build_Tree(rson);
Push_Up(rt);
}
int64 Query_Tree(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) return Min[rt];
int m = (l + r) >> 1;
int64 temp = INF;
if (m >= L) temp = min(temp,Query_Tree(L,R,lson));
if (m + 1 <= R) temp = min(temp,Query_Tree(L,R,rson));
return temp;
}
void Update(int L,int64 x,int l,int r,int rt) {
if (l == r) {
Min[rt] = min(Min[rt],x);
return;
}
int m = (l + r) >> 1;
if (L <= m) Update(L,x,lson);
else Update(L,x,rson);
Push_Up(rt);
}
int main()
{
int i,j,k,t,cas = 0;
scanf("%d",&t);
while (t--) {
scanf("%d%d",&n,&m);
cnt = tot = 1;
for (i = 1; i <= n; ++i) {
scanf("%d%d%d",&arr[i].end,&arr[i].beg,&arr[i].time);
dis[cnt++] = arr[i].beg,dis[cnt++] = arr[i].end;
}
DisCret(); //离散化
Build_Tree(1,tot,1); //构建线段树
sort(arr+1,arr+1+n,cmp); //排序后才没有后效性
for (i = 1; i <= n; ++i) {
int64 tp = Query_Tree(arr[i].beg,arr[i].end,1,tot,1);
if (tp == INF) continue;
Update(arr[i].end,tp+arr[i].time,1,tot,1); //dp[arr[i].end] = min(dp[k]) + arr[i].time;
}
ans = Query_Tree(Binary(m),tot,1,tot,1);
if (ans == INF) printf("Case #%d: -1\n",++cas);
else printf("Case #%d: %lld\n",++cas,ans);
}
}
本文ZeroClock原创,但可以转载,因为我们是兄弟。
分享到:
相关推荐
uestc微处理器体系结构嵌入式系统设计 计算机系统组成与体系结构PPT教案.pptx
UESTC_Daily_Body_Temperature_Report 成电/电子科技大学每日体温上报 现在每天都要上报体温,这有点烦人,而且还有偶尔会忘记的情况,该项目利用Github的操作实现每日体温自动上报 使用简介 这个项目写的很简单,...
uestc微处理器体系结构嵌入式系统设计微处理器体系结构PPT学习教案.pptx
uestc微处理器体系结构嵌入式系统设计计算机系统组成与体系结构学习课程.pptx
uestc微处理器体系结构嵌入式系统设计计算机系统组成与体系结构PPT学习教案.pptx
uestc_os_exp:UESTC操作系统实验
在电子科大本科期间所有课程课设和作业的代码和部分报告,包括【计算机组成与结构】、【计算机网络与通信技术】、【软件基础综合课程设计】、【互联网软件开发综合课程设计】、【数据挖掘与大数据分析】、【时间序列...
电子科技大学官方论坛评优记分板
UESTC考研倒计时 可以记录考研倒计时
uestc图书馆联网利器。您是否为图书馆无法联网而苦恼过,快来下载吧
C++编辑和编译系统采用Visual Studio 2010,设计1个综合运用数据封装、继承、运算符重载、多态等机制的C++编程语言的应用实验“学校教职工工资管理程序”:对学校教职工进行关系划分;着重应用数据封装、继承等机制...
注意【指导老师为阎炜】,仅供参考,学到真本事更重要。 内容: 1、求阶乘 2、在100-1000之间有多少个其数字之和等于9而且该数可被5整除的整数? ……
uestc_python电子科技大学2020-2021python选修课使用概述数据库迁移1.1 py manage.py makemigrations 1.2 py manage.py migrate创建超级用户2.1 py manage.py createsuperuser启动服务3.1 py manage.py runserver...
uestc 的清水河上网脚本,大家可以参考下怎么写shell,写的不错
一份UESTC的ACM题目推荐,可以当作入门题来切
8介绍系统时钟和硬件定时器,单处理器和多处理器上的linux计时体系结构,定时的时间插补原理,单处理器和多处理器上的时钟中断处理,动态定时器的数据结构和算法原理,定时器竞争情形,延迟函数。Time,...
微信小程序源码-Cheese-UESTC-master 校内新闻大图版小程序
注意【指导老师为周川】,仅供参考,学到真本事更重要。 内容: 实验1、 分别利用点、线图元生成锥形螺旋曲线和环形螺旋曲线,要求可以设置点的大小、线可以设置线形和宽度。 在窗口中绘制三角形和四边形两个简单...
BUAA_CST_LaTeX_report LaTeX_report_BUAA_CST(供私人使用),基于UESTC_report_latex自用LaTeX模板(北航),基于修改