首页 > 代码库 > hdu1160(最长上升子序列)

hdu1160(最长上升子序列)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1160

题意:给定一些小猫的属性:体重和速度。然后求某些猫顺序的排列,使得体重上升,速度下降,这样的排列尽量长。

分析:主要将速度按从大到小排序,然后对体重求最长上升子序列即可,这里因为要记录路径,所以只能O(n^2)求解。

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 1<<30#define N 2010using namespace std;struct node{    int w,s,num;    bool operator<(const node a)const    {        return (s>a.s||(s==a.s&&w<a.w));    }}t[1010];int dp[1010],path[1010];void print(int x)//输出路径{    if(path[x]==-1)    {        printf("%d\n",x);        return;    }    print(path[x]);    printf("%d\n",x);}int main(){    int n=0;   // freopen("in.txt","r",stdin);    while(scanf("%d%d",&t[n].w,&t[n].s)!=EOF)t[n].num=n+1,n++;    sort(t,t+n);    memset(dp,0,sizeof(dp));    memset(path,-1,sizeof(path));    int mx=0,id;    for(int i=0;i<n;i++)    {        dp[i]=1;        for(int j=0;j<i;j++)        if(t[j].w<t[i].w&&dp[i]<=dp[j]+1)        {            dp[i]=dp[j]+1;            path[t[i].num]=t[j].num;        }        if(dp[i]>mx)        {            mx=dp[i];            id=t[i].num;        }    }    printf("%d\n",mx);    print(id);}
View Code

 

hdu1160(最长上升子序列)