hdu1160 最大上升子序列问题+输出路径

清疚 2022-08-20 15:08 120阅读 0赞

题意：

就是在一个序列里面找出最长的子序列，这个序列中体积上升，速度下降。

分析：

就是按体积排序之后素的的找出最大下降子序列就可以了，麻烦一点的就是需要输出顺序。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include<stack>
    using namespace std;
    
    const int maxn = 1005;
    struct node{
        int w,v,num;
    }mouse[maxn];
    
    int dp[maxn];
    int path[maxn];
    
    int cmp(node a1,node a2)
    {
        if(a1.w!=a2.w) return a1.w<a2.w;
        else return a1.v>a2.v;
    }
    int main()
    {
        int cnt=0;
        while( scanf("%d%d",&mouse[cnt].w,&mouse[cnt].v)!=EOF )
        {
            mouse[cnt].num=cnt+1;
            path[cnt]=-1;
            cnt++;
        }
        sort(mouse,mouse+cnt,cmp);
        int max_dp,max_num;
        max_dp=max_num=0;
        dp[0]=1;
    
        for(int i = 1 ; i < cnt ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(mouse[j].v>mouse[i].v && mouse[j].w!=mouse[i].w )
                {
                    if(dp[i]<dp[j]+1)
                    {
                        dp[i] = dp[j]+1 ;
                        path[i]=j;
                    }
                }
            }
            if(max_dp<dp[i])
            {
                max_dp=dp[i];
                max_num=i;
            }
        }
    
        stack<int>s;
        s.push(mouse[max_num].num);
        while(path[max_num]!=-1 )
        {
            s.push(mouse[path[max_num]].num);
            max_num=path[max_num];
        }
        printf("%d\n",s.size());
        while( !s.empty() )
        {
            printf("%d\n",s.top() );
            s.pop();
        }
        return 0;
    }