背景
你知道吗,SQ Class的人都很喜欢打CS。(不知道CS是什么的人不用参加这次比赛)。
描述
今天,他们在打一张叫DUSTII的地图,万恶的*要炸掉藏在A区的SQC论坛服务器!我们SQC的人誓死不屈,即将于*展开激战,准备让一个人守着A区,这样*就不能炸掉服务器了。(一个人就能守住??这人是机械战警还是霹雳游侠?)
但是问题随之出现了,由于DustII中风景秀丽,而且不收门票,所以n名反恐精英们很喜欢在这里散步,喝茶。他们不愿意去单独守在荒无人烟的A区,在指挥官的一再命令下,他们终于妥协了,但是他们每个人都要求能继续旅游,于是给出了自己的空闲时间,而且你强大的情报系统告诉了你恐怖份子计划的进攻时间(从s时刻到e时刻)。
当然,精明的SQC成员不会为你免费服务,他们还要收取一定的佣金(注意,只要你聘用这个队员,不论他的执勤时间多少,都要付所有被要求的佣金)。身为指挥官的你,看看口袋里不多的资金(上头真抠!),需要安排一个计划,雇佣一些队员,让他们在保证在进攻时间里每时每刻都有人员执勤,花费的最少资金。
格式
输入格式
第一行是三个整数n(1≤n≤10000),s和e(1≤s≤e≤90000)。
接下来n行,描述每个反恐队员的信息:空闲的时间si, ei(1≤si≤ei≤90000)和佣金ci(1≤ci≤300000)。
输出格式
一个整数,最少需支付的佣金,如果无解,输出“-1”。
样例1
样例输入1
3 1 5
1 3 3
4 5 2
1 1 1
样例输出1
5
限制
提示
敌人从1时刻到4时刻要来进攻,一共有3名反恐队员。第1名从1时刻到3时刻有空,要3元钱(买糖都不够??)。以此类推。
一共要付5元钱,选用第1名和第2名。
来源
SQ CLASS公开编程竞赛2008——Problem D
Source: WindTalker, liuichou, royZhang
题目大意
数轴上有一些区间,每个区间有一个费用。要求选择一些区间将$[s, t]$覆盖,问最小的总费用。
Solution#1 Dynamic Programming & Heap Optimization
dp是显然的。 用$f[i]$表示将$[s, i]$覆盖的最小费用。
考虑转移。显然通过能够覆盖点$i$的线段进行转移,因此有
$f[i] = \max_{线段j能覆盖点i}\left\{ f[l_{j} - 1] + w_{j}\right\}$
显然可以用一个堆维护右边的那一坨。
Code
/**
* Vijos
* Problem#1404
* Accepted
* Time: 98ms
* Memory: 3.48m
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long typedef class Segment {
public:
int l, r;
int w; Segment(int l = , int r = , int w = ):l(l), r(r), w(w) { } boolean operator < (Segment b) const {
return l < b.l;
}
}Segment; typedef class Heap {
public:
priority_queue<ll, vector<int>, greater<int> > que;
priority_queue<ll, vector<int>, greater<int> > del; Heap() { } ll top() {
while (!del.empty() && que.top() == del.top())
que.pop(), del.pop();
return que.top();
} void push(ll x) {
que.push(x);
} void remove(ll x) {
del.push(x);
} boolean empty() {
return (que.size() == del.size());
}
}Heap; int n, s, t;
Segment* ss;
vector<Segment*> *g;
Heap h;
ll *f; inline void init() {
scanf("%d%d%d", &n, &s, &t);
ss = new Segment[(n + )];
g = new vector<Segment*>[(t - s + )];
f = new ll[(t - s + )];
t = t - s + ;
for (int i = ; i <= n; i++) {
scanf("%d%d%d", &ss[i].l, &ss[i].r, &ss[i].w);
ss[i].l = max(ss[i].l - s, ) + ;
ss[i].r = max(ss[i].r - s, ) + ;
if (ss[i].r > t) ss[i].r = t;
}
} inline void solve() {
int p = ;
f[] = ;
sort (ss + , ss + n + );
for (int i = ; i <= t; i++) {
while (p <= n && ss[p].l == i) {
h.push(f[ss[p].l - ] + ss[p].w);
g[ss[p].r].push_back(ss + p);
p++;
}
if (h.empty()) {
puts("-1");
return;
}
f[i] = h.top();
for (int j = ; j < (signed)g[i].size(); j++)
h.remove(f[g[i][j]->l - ] + g[i][j]->w);
g[i].clear();
}
printf(Auto"\n", f[t]);
} int main() {
init();
solve();
return ;
}
Solution 1
Solution#2 Shortest Path & Segment Tree Optimization
其实把dp的转移变成边,然后发现巧的是每条区间的前一个点,向区间上的所有整点连边。
于是写个线段树建图优化(其实没什么高端的,就是建虚点,防止重复的连边,然后再加点连边的技巧就好了)。
Code
/**
* Vijos
* Problem#1404
* Accepted
* Time: 606ms
* Memory: 16.0m
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long
#define pii pair<int, int>
#define fi first
#define sc second const signed ll llf = (signed ll) (~0ull >> ); int n, s, t;
vector<pii> *g;
ll *f;
boolean *vis; inline void init() {
scanf("%d%d%d", &n, &s, &t);
t = t - s + ;
int siz = ((t + ) << ) + ;
g = new vector<pii>[siz];
f = new ll[siz];
vis = new boolean[siz];
fill(vis, vis + siz, false);
fill(f, f + siz, llf >> );
} void build(int p, int l, int r) {
if (l == r) return;
int mid = (l + r) >> ;
g[p].push_back(pii(p << , ));
g[p].push_back(pii((p << ) | , ));
build(p << , l, mid);
build((p << ) | , mid + , r);
} int query(int p, int l, int r, int idx) {
if (l == r)
return p;
int mid = (l + r) >> ;
if (idx <= mid)
return query(p << , l, mid, idx);
return query((p << ) | , mid + , r, idx);
} void query(int p, int l, int r, int ql, int qr, int st, int w) {
if (l == ql && r == qr) {
g[st].push_back(pii(p, w));
return;
}
int mid = (l + r) >> ;
if (qr <= mid)
query(p << , l, mid, ql, qr, st, w);
else if (ql > mid)
query((p << ) | , mid + , r, ql, qr, st, w);
else {
query(p << , l, mid, ql, mid, st, w);
query((p << ) | , mid + , r, mid + , qr, st, w);
}
} inline void build() {
build(, , t);
for (int i = , l, r, w; i <= n; i++) {
scanf("%d%d%d", &l, &r, &w);
l = max(l - s, ) + ;
r = max(r - s, ) + ;
if (r > t) r = t;
int id = query(, , t, l - );
query(, , t, l, r, id, w);
}
} queue<int> que;
inline void spfa(int s) {
que.push(s);
f[s] = ;
while (!que.empty()) {
int e = que.front();
que.pop();
vis[e] = false;
for (int i = ; i < (signed)g[e].size(); i++) {
int eu = g[e][i].fi, w = g[e][i].sc;
if (f[e] + w < f[eu]) {
f[eu] = f[e] + w;
if (!vis[eu]) {
vis[eu] = true;
que.push(eu);
}
}
}
}
} inline void solve() {
int is = query(, , t, );
int it = query(, , t, t);
spfa(is);
if (f[it] == (llf >> ))
puts("-1");
else
printf(Auto"\n", f[it]);
} int main() {
init();
build();
solve();
return ;
}
Solution 2
Solution#3 Shortest Path
wtf?纯最短路?没逗我?
每个区间的前一个点向区间结束点连边。然后每个点向它的前一个点连边,权值为0。
(神奇的建图方法。。)
看起来非常朴素,竟然没有dp快
Code
/**
* Vijos
* Problem#1404
* Accepted
* Time: 285ms
* Memory: 5.75m
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long
#define pii pair<int, int>
#define fi first
#define sc second const signed ll llf = (signed ll) (~0ull >> ); int n, s, t;
vector<pii> *g;
ll *f;
boolean *vis; inline void init() {
scanf("%d%d%d", &n, &s, &t);
t = t - s + ;
g = new vector<pii>[t + ];
f = new ll[t + ];
vis = new boolean[t + ];
fill(vis, vis + t + , false);
fill(f, f + t + , llf >> );
} inline void build() {
for (int i = , l, r, w; i <= n; i++) {
scanf("%d%d%d", &l, &r, &w);
l = max(l - s, ) + ;
r = max(r - s, ) + ;
if (r > t) r = t;
g[l - ].push_back(pii(r, w));
}
for (int i = ; i <= t; i++)
g[i].push_back(pii(i - , ));
} queue<int> que;
inline void spfa(int s) {
que.push(s);
f[s] = ;
while (!que.empty()) {
int e = que.front();
que.pop();
vis[e] = false;
for (int i = ; i < (signed)g[e].size(); i++) {
int eu = g[e][i].fi, w = g[e][i].sc;
if (f[e] + w < f[eu]) {
f[eu] = f[e] + w;
if (!vis[eu]) {
vis[eu] = true;
que.push(eu);
}
}
}
}
} inline void solve() {
spfa();
if (f[t] == (llf >> ))
puts("-1");
else
printf(Auto"\n", f[t]);
} int main() {
init();
build();
solve();
return ;
}
Vijos 1404 遭遇战 - 动态规划 - 线段树 - 最短路 - 堆的更多相关文章
-
Vijos 1404 遭遇战
Vijos 1404 遭遇战 背景 你知道吗,SQ Class的人都很喜欢打CS.(不知道CS是什么的人不用参加这次比赛). 描述 今天,他们在打一张叫DUSTII的地图,万恶的*要炸掉藏在A区 ...
-
BZOJ_1672_[Usaco2005 Dec]Cleaning Shifts 清理牛棚_动态规划+线段树
BZOJ_1672_[Usaco2005 Dec]Cleaning Shifts 清理牛棚_动态规划+线段树 题意: 约翰的奶牛们从小娇生惯养,她们无法容忍牛棚里的任何脏东西.约翰发现,如果要使这群 ...
-
2019牛客多校第一场 I Points Division(动态规划+线段树)
2019牛客多校第一场 I Points Division(动态规划+线段树) 传送门:https://ac.nowcoder.com/acm/contest/881/I 题意: 给你n个点,每个点有 ...
-
【bzoj5210】最大连通子块和 树链剖分+线段树+可删除堆维护树形动态dp
题目描述 给出一棵n个点.以1为根的有根树,点有点权.要求支持如下两种操作: M x y:将点x的点权改为y: Q x:求以x为根的子树的最大连通子块和. 其中,一棵子树的最大连通子块和指的是:该子树 ...
-
Codeforces 834D The Bakery - 动态规划 - 线段树
Some time ago Slastyona the Sweetmaid decided to open her own bakery! She bought required ingredient ...
-
Codeforces787D(SummerTrainingDay06-D 线段树+最短路)
D. Legacy time limit per test:2 seconds memory limit per test:256 megabytes input:standard input out ...
-
vijos 1659 河蟹王国 线段树区间加、区间查询最大值
河蟹王国 Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 https://vijos.org/p/1659 Description 河蟹王国有一位河蟹国王,他 ...
-
Codeforces 787D Legacy 线段树 最短路
题意: 有\(n(1 \leq n \leq 10^5)\)个点,\(q(1 \leq q \leq 10^5)\)条路和起点\(s\) 路有三种类型: 从点\(v\)到点\(u\)需要花费\(w\) ...
-
786B - Legacy(线段树 + 最短路)线段树优化建图
题意: 就是给定一张n nn个点的图,求源点s ss到每个点的单源最短路.这张图共有q组边,连边方式有3种: a→b ,边权为w的单向边:a→[l,r] ,即a到连续区间[l,r]中的每一个点都有一条 ...
随机推荐
-
for(String s:v)
s是遍历后赋值的变量,v是要遍历的list.可以通过以下语句进行测试: List<String> v=new ArrayList(); v.add("one"); v. ...
-
bootstrap-js(4)标签页
实例 标签页(Tab)在 Bootstrap 导航元素 一章中介绍过.通过结合一些 data 属性,您可以轻松地创建一个标签页界面. 通过这个插件您可以把内容放置在标签页或者是胶囊式标签页甚至是下拉菜 ...
-
nodejs使用connect-mongodb报错(Please ensure that you set the default write concern)
原本是使用connect-mongo的,可能是express版本号的升级报错了.改用connect-mongodb.可是使用后出现了例如以下的警告: G:\nodejs\moviesite>gr ...
-
thinkphp中定义自己的函数
可以在前台和后台的公共文件夹中common.php中定义自己的函数,这样就可以在控制器中调用,而不需要调用对象了 /** * @name addvtorandp * @author 黄峰1664253 ...
-
mac 中git操作账号的保存与删除
保存: 在mac中自动保存git的用户名和密码很简单,只需要在终端命令行中输入下面的命令就是: git config --global credential.helper osxkeychain 然后 ...
-
【原创】驱动加载之OpenService
SC_HANDLE WINAPI OpenService( _In_ SC_HANDLE hSCManager, _In_ LPCTSTR lpServiceName, _In_ DWORD dwDe ...
-
SpringMVC.入门篇.一.HelloWorld
SpringMVC.入门篇<一>HelloWorld 项目包结构如下: HelloController.java 代码 package com.charles.controller; im ...
-
web服务器和数据库服务器分离的优势
一般我们服务器都是分开的,网页服务器.数据服务器单独配置. web服务器不掉,那么就可以正常使用,data服务器掉了,那么web还可以坚持一会. 如果是web服务器掉了,那么就上不去了,不过有一些设置 ...
-
$trainClassLayer.find(&#39;input[name=data-item-checkbox]&#39;).eq(index).change();//激活第index+1那个checkbox
☆ $.each(data, function (index, org) { if (org.alreadySent) { $trainClassLayer.find('input[name=data ...
-
Linux文件系统操作
1:查看磁盘使用情况 df [-选项] 目录名 2:查看目录下文件大小 du 目录名称 3:实体链接 创建inode产生一个新文件名,链接到一个已有的文件. 限制:不能垮文件系统进行实体链接:不能链接 ...