UOJ Logo kb的博客

博客

友好城市题解

2018-12-07 18:02:30 By kb

这道题不就是最长不下降子序列,建议回去看看

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    #define kb 5010

    struct Edge{
        int from, to;
    }E[kb];
    int dp[kb];
    bool map[kb][kb];

    bool cmp(Edge a, Edge b)
    {
        if(a.from>b.from)
            return false;
        else
            return true;
    }

    int main()
    {
        int n, u, v;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &E[i].from, &E[i].to);
            dp[i]=1;
        }
        sort(E+1, E+n+1, cmp);
        for(int i=2; i<=n; i++)
            for(int j=1; j<i; j++)
                if(E[j].to<=E[i].to)
                    dp[i]=max(dp[i], dp[j]+1);
        int max=0;
        for(int i=1; i<=n; i++)
            if(dp[i]>dp[max])
                max=i;
        printf("%d", dp[max]);
        return 0;
    }

emm,就是这个,我之前打的是sort不对好吧,不要复制

评论

NaCl
tql
xiapuR
tql

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。