CF459E-DP

核心代码15行

思路

观察数据范围，我们建m层分层图跑最短路想到DP。

DP最大的特点就是无后效性。那么我们这一题哪个条件无后效性呢？

发现DP值一定从边权小于当前点的位置转移而来。

这不就无后效性了？我们按边权将所有边排序即可。

然后，枚举边，将DP值记录到点上，每次用起始点的dp值加1更新到达点的dp值。最后输出dp值最大的即可。

然后，您会发现第一个样例过不去。

因为题目要求边权严格递增，所以我们需要同时将边权相同的边用上次的dp值更新，即我们需要临时记录一下。

样例非常良心。

实现

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read(){

	int w=0,x=0;char c=getchar();

	while(!isdigit(c))w|=c=='-',c=getchar();

	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

	return w?-x:x;

}

namespace star

{

	const int maxn=3e5+10;

	int n,m,f[maxn],g[maxn];

	struct edge{

		int u,v,val;

		inline bool operator < (const edge &zp)const{return val<zp.val;}

	}e[maxn];

	inline void work(){

		n=read();m=read();

		for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),e[i].val=read();

		sort(e+1,e+1+m);

		for(int i=1,j;i<=m;i=j+1){

			j=i;

			while(e[j+1].val==e[i].val)j++;

			for(int k=i;k<=j;k++) g[e[k].u]=f[e[k].u],g[e[k].v]=f[e[k].v];//只有这些dp值要用

			for(int k=i;k<=j;k++) f[e[k].v]=max(f[e[k].v],g[e[k].u]+1);

		}

		int ans=0;

		for(int i=1;i<=n;i++) ans=max(ans,f[i]);

		printf("%d",ans);

	}

}

signed main(){

	star::work();

	return 0;

}

postscripts

目前rank1，可能只是因为写的人少。

是一道不错的DP练手题。

巴特西

CF459E-DP

CF459E-DP

思路

实现

postscripts

最新文章

热门文章