NYOJ1208 水题系列（DP）

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=1208

大意： 给你一个有向图，每条边都有一定的权值，现在让你从图中的任意一点出发，每次走的边的权值必须必上一次的权值大的情况下，问你最多能走几条边？
这道题最容易想到的， 就是最长单调递增子序列；但是在这道题上是超时的。 
每次走到边的权值必须比上一次的大， 所以我们可以先把所有的边按权值进行从小到大的排序。
在定义状态 DP【i】 为走到第i条边经过最多的边的个数。
                   g【j】 为走到点j所经过的最多的边的个数。
则DP【i】 = g【sa[i].from】 + 1;  最后的结果就是DP[I]中的最大值；

这里还有一个要注意的点就是相等权值边只能走一次，所以g数组就不能每条边的更新了， 而是把具有相同权值的边都DP【i】都更新完了， 再回来更新具有相等权值的g【j】点的值。为什么这样呢，大家可以想一下第一组样例就明白了。如果进行延迟更新的话，一组样例就会输出3， 就相当于同一权值的边走了多次， 就与题意不符了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 100000 + 10;
struct Info
{
    int from, to, val;
}sa[maxn];
int cmp(Info a, Info b)
{
    return a.val < b.val;
}
int dp[maxn], g[maxn];
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < m; i++)
            scanf("%d%d%d", &sa[i].from, &sa[i].to, &sa[i].val);
        sort(sa, sa+m, cmp);
        memset(g, 0, sizeof(g));
        int ans = 0, t = 0;
        for(int i = 0; i < m; i++)
        {
            dp[i] = g[sa[i].from] + 1;
            if(sa[i].val != sa[i+1].val)//延迟更新g
            {
                for(int j = t; j <= i; j++)
                    g[sa[j].to] = max(g[sa[j].to], dp[j]);
                t = i + 1;
            }
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}