题目链接

动态规划转化成 DAG 然后拓扑求解的思路

虽然很简单不过感觉这个新思路会很有用!

如果两个事件互不影响并且有先后关系,就可以连一条有向边,跑最长路可以得到最后的最优解

实际上这还是个背包……

 #include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = + ;
int n, m, r, head[maxn], dis[maxn], in_deg[maxn], edge_num, ans; struct Segment {
int lef, rig, enr;
inline bool operator < (const Segment &x) const{ return this->rig < x.rig; }
} seg[maxn]; struct Edge { int v, nxt; } edge[maxn * maxn]; inline int read() {
register char ch = ; register int w = , x = ;
while( !isdigit(ch) ) w |= (ch == '-'),ch = getchar();
while( isdigit(ch) ) x = (x * ) + (ch ^ ), ch = getchar();
return w ? -x : x;
} inline void Add_edge(int u, int v) {
edge[++edge_num].v = v;
edge[edge_num].nxt = head[u], head[u] = edge_num;
} inline void Breath_fs() {
queue<int> q;
for(int i = ; i <= m; ++i) dis[i] = seg[i].enr;
for(int i = ; i <= m; ++i) if( !in_deg[i] ) q.push(i);
while( !q.empty() ) {
int x = q.front(); q.pop();
for(int i = head[x]; i; i = edge[i].nxt) {
if( dis[edge[i].v] < dis[x] + seg[edge[i].v].enr )
dis[edge[i].v] = dis[x] + seg[edge[i].v].enr;
if( --in_deg[edge[i].v] == ) q.push(edge[i].v);
}
}
} int main(int argc, char const *argv[])
{
freopen("nanjolno.in", "r", stdin);
freopen("nanjolno.out", "w", stdout); scanf("%d%d%d", &n, &m, &r);
for(int i = ; i <= m; ++i)
seg[i].lef = read(), seg[i].rig = read() + r, seg[i].enr = read();
sort(seg + , seg + m + ), ans = ;
for(int i = ; i <= m; ++i) for(int j = i + ; j <= m; ++j)
if( seg[i].rig <= seg[j].lef ) Add_edge(i, j), ++in_deg[j];
Breath_fs();
for(int i = ; i <= m; ++i) ans = max(ans, dis[i]);
printf("%d\n", ans); fclose(stdin), fclose(stdout);
return ;
}

—— 冬天来了 —— 那是悲喜交加,永远的瞬间。

最新文章

  1. sql注入时易被忽略的语法技巧以及二次注入
  2. [MySQL] 关系型数据库的设计范式 1NF 2NF 3NF BCNF
  3. CentOS 6.4下PXE+Kickstart无人值守安装操作系统 转
  4. 关于lambda表达式在javascript中的使用
  5. sql server 时间
  6. oc-14-对象方法调用类方法
  7. 编写3个不同版本的程序,令其均能输出ia的元素
  8. ionic(一) build你的第一个android apk
  9. jquery mobile 前言
  10. 大众点评的大数据实践-CSDN.NET
  11. 【Python】python 多线程两种实现方式
  12. 宽带连接工具[bat]
  13. MyBatis 一对一关联查询
  14. React 16.3来了:带着全新的Context API
  15. 从DataTable中查询数据
  16. Xshell配合Screen之ssh会话永不断开
  17. dotnet core 3.0 linux 部署小贴士
  18. Spring保护方法
  19. 远程shell脚本执行工具类
  20. HTTP长连接和短连接 + Websocket

热门文章

  1. Java线程的创建方式三:Callable(四)
  2. CSS3 flexbox 布局 ---- flex 容器属性介绍
  3. CF980E
  4. POJ 2823 滑动窗口 单调队列
  5. Nginx 网络事件
  6. Spring MVC 使用介绍(二)—— DispatcherServlet
  7. linux-shell系列4-init
  8. ajax 提交Dictionary
  9. 初步了解HTML
  10. 洛谷P1622释放囚犯