FatMouse's Speed

HDOJ-1160

注意输出长度的时候不是输出dp[n]
#include<bits/stdc++.h>

using namespace std;

const int maxn=1003;

const int INF=0X3F3F3F3F;

int w[maxn];//weight

int s[maxn];//speed

int dp[maxn];//dp[i]表示以i结尾的最长上升子序列的长度

struct node{

    int weight;

    int speed;

    int num;

    bool operator<(const node& t)const{

        if(weight<t.weight&&speed>t.speed){

            return true;

        }else{

            return false;

        }

    }

};

bool cmp(const node&a,const node& b){

    if(a.weight==b.weight){

        return a.speed>b.speed;

    }else return a.weight<b.weight;

}

node mice[maxn];

int father[maxn];

int main(){

    int n=0;

    int i=1;

    while(cin>>w[i]>>s[i]){

        mice[i]=node{w[i],s[i],i};

        i++;

        n++;

    }

    memset(dp,-INF,sizeof(dp));

    sort(mice+1,mice+n+1,cmp);

    memset(father,-1,sizeof(father));

    for(i=1;i<=n;i++){

        dp[i]=1;

        for(int j=1;j<i;j++){

            if(mice[j]<mice[i]){

                if(dp[j]+1>dp[i]){

                    dp[i]=dp[j]+1;

                    father[i]=j;

                }

            }

        }

    }

    int maxs=-INF;

    int maxi=0;

    for(i=1;i<=n;i++){

        //cout<<dp[i]<<endl;

        if(dp[i]>maxs){//没有等于

            maxs=dp[i];

            maxi=i;

        }

    }

    cout<<maxs<<endl;//注意这里不是直接输出dp[n],因为dp[i]表示以i结尾的子序列的最大长度，但这可能不是最终答案的最大长度。

    i=maxi;

    vector<int> v;

    for(;i!=-1;i=father[i]){

        v.push_back(mice[i].num);

        //cout<<mice[i].num<<endl;

    }

    reverse(v.begin(),v.end());

    for(int i=0;i<v.size();i++){

        cout<<v[i]<<endl;

    }

    //system("pause");

    return 0;

}
巴特西

HDOJ-1160(最长上升子序列变形)

FatMouse's Speed

HDOJ-1160

最新文章

热门文章
