题意:给一个有向图带权图,求最长严格递增链的长度。
分析:
定义 dp(i) 以 节点 i 开头的最长长度,要保证上一条边很长,而且权值很小,很难把控。
定义 f(i) 以节点 i 结尾的最长长度。 但是要严格递增,节点节点间转移也不好搞,于是以边为对象。
首先对边排序分层,后面的边,一定大于等于前面的边,用前面一层的边,跟新后面的一层的节点。
f[e[k].v] = max(f[e[k].v]+f[e[k].u+1])
但是,这样是不对的,原因是严格递增这里,若在同一层里面,有1->2->3,权值是1,那么就没有做到严格递增了。
而是累加起来了。
这里用一个临时变量存下来,存下之前能得到最长长度。
#includeusing 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