8/2 训练日志(dp+思维+字典树)

​

活动地址：CSDN21天学习挑战赛

E. Pashmak and Graph

题意：给定一张带权值的有向图，n个顶点m条边，找出一条长度最大权值递增的路径，输出长度。 思路： 1.若是以每个点都进行一次遍历，必定会超时；g[i]表示在到达i点时满足题意得长度最大是多少 2.还需将权值进行升序排列，前面权值小的肯定先经过 3.再开一数组，dp[i]表示第i条边结尾的最大长度 4.状态转移方程：dp[i]=g[e[i].u]+1

#include
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m,g[N],dp[N];
struct node
{
    int u,v,w;
    bool operator n>>m;
    for(int i=1;i>u>>v>>w;
        e[i]=(node){u,v,w};
    }
    sort(e+1,e+m+1);
    int ans=0,k=1;
    e[m+1].w=-1;
    for(int i=1;i