博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces 459E
阅读量:5213 次
发布时间:2019-06-14

本文共 654 字,大约阅读时间需要 2 分钟。

题意:给一个有向图带权图,求最长严格递增链的长度。

分析:

定义 dp(i) 以 节点 i 开头的最长长度,要保证上一条边很长,而且权值很小,很难把控。

定义 f(i) 以节点 i 结尾的最长长度。 但是要严格递增,节点节点间转移也不好搞,于是以边为对象。

首先对边排序分层,后面的边,一定大于等于前面的边,用前面一层的边,跟新后面的一层的节点。

f[e[k].v] = max(f[e[k].v]+f[e[k].u+1])

但是,这样是不对的,原因是严格递增这里,若在同一层里面,有1->2->3,权值是1,那么就没有做到严格递增了。

而是累加起来了。

这里用一个临时变量存下来,存下之前能得到最长长度。

#include 
using namespace std;const int maxn = 300000+5;struct Edge { int u,v,w; bool operator < (const Edge & rhs) const { return w < rhs.w; }}e[maxn];int d[maxn],f[maxn];int main(int argc, char const *argv[]){ int n,m; scanf("%d%d",&n,&m); for(int i = 0;i

 

转载于:https://www.cnblogs.com/TreeDream/p/7251310.html

你可能感兴趣的文章
路冉的JavaScript学习笔记-2015年1月23日
查看>>
Mysql出现(10061)错误提示的暴力解决办法
查看>>
2018-2019-2 网络对抗技术 20165202 Exp3 免杀原理与实践
查看>>
NPM慢怎么办 - nrm切换资源镜像
查看>>
CoreData 从入门到精通(四)并发操作
查看>>
Swift - UIView的常用属性和常用方法总结
查看>>
Swift - 异步加载各网站的favicon图标,并在单元格中显示
查看>>
Java编程思想总结笔记Chapter 5
查看>>
[LeetCode]662. Maximum Width of Binary Tree判断树的宽度
查看>>
WinForm聊天室
查看>>
Python 从零学起(纯基础) 笔记(一)
查看>>
【Python学习笔记】1.基础知识
查看>>
梦断代码阅读笔记02
查看>>
Java 线程安全问题
查看>>
selenium学习中遇到的问题
查看>>
大数据学习之一——了解简单概念
查看>>
P1-13:集成日志组件 logback 2彩色日志
查看>>
Linux升级内核教程(CentOS7)
查看>>
Lintcode: Partition Array
查看>>
分享适合个人站长的5类型网站
查看>>