CF459E-DP
核心代码15行
思路
观察数据范围，我们建m层分层图跑最短路想到DP。
DP最大的特点就是无后效性。那么我们这一题哪个条件无后效性呢？
发现DP值一定从边权小于当前点的位置转移而来。
这不就无后效性了？我们按边权将所有边排序即可。
然后，枚举边，将DP值记录到点上，每次用起始点的dp值加1更新到达点的dp值。最后输出dp值最大的即可。
然后，您会发现第一个样例过不去。
因为题目要求边权严格递增，所以我们需要同时将边权相同的边用上次的dp值更新，即我们需要临时记录一下。
样例非常良心。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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];
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练手题。
