UVA 10131 Is Bigger Smarter? 【严格单调递增子序列】

àì夳堔傛蜴生んèń 2022-08-12 01:59 116阅读 0赞

题目：[UVA 10131Is Bigger Smarter][]

题意：给出大象的身高和体重，求身高递增且体重递减的最长序列，都是严格的，并打印序列。

分析：就是先对身高按自增排序，然后求一个单调递减子序列，严格单调的，所以加一句判断，然后打印序列，用一个数组保存就好了

开始想的是先预处理掉重复的，提交wa了，这样不行，因为你不知道体重是最高的还是最低的，可能开始留高的好，后面低的比较好。所以.....

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include <map>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int N = 2000;
    const int inf = 0x3f3f3f3f;
    struct Node
    {
        int w,h;
        int num,dp;
    };
    vector<Node> v;
    vector<int> ans;
    int cmp(Node a,Node b)
    {
        if(a.w!=b.w)
            return a.w<b.w;
    }
    int father[N];
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int cnt=1;
        Node tmp;
        while(~scanf("%d%d",&tmp.w,&tmp.h)) //输入
        {
            tmp.num=cnt++;
            tmp.dp=0;
            v.push_back(tmp);
        }
        sort(v.begin(),v.end(),cmp);
        memset(father,0,sizeof(father));
        v[0].dp=1;
        bool ok=false;
        int count=0,ss=1,ttp=1;
        for(int i=1; i<v.size(); i++)
        {
            int ff=0,cas=0;
            for(int j=i-1; j>=0; j--)
            {
                if(v[i].h<v[j].h && v[i].w!=v[j].w)
                {
                    if(ff<v[j].dp)
                    {
                        ff=v[j].dp;
                        cas=j;
                    }
                }
            }
            v[i].dp=ff+1;
            father[i]=cas;
            if(count<v[i].dp)
            {
                count=v[i].dp;
                ss=i;
                if(ok)
                {
                    ttp=i;
                    ok=true;
                }
            }
        }
        printf("%d\n",count);
        for(int i=ss;i>=ttp;i=father[i])
        {
            ans.push_back(v[i].num);
        }
        for(int i=ans.size()-1;i>=0;i--)
            printf("%d\n",ans[i]);
        v.clear();
        v.clear();
        ans.clear();
        return 0;
    }

[UVA 10131Is Bigger Smarter]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1072