HDU 1160 FatMouse's Speed （最长有序的上升子序列）-白红宇

HDU 1160 FatMouse's Speed （最长有序的上升子序列）

阅读量：5056 次

发布时间：2019-06-12

本文共 1324 字，大约阅读时间需要 4 分钟。

题意：给你一系列个w，s。要你找到最长的n使得

W[m[1]] < W[m[2]] < ... < W[m[n]]

and

S[m[1]] > S[m[2]] > ... > S[m[n]]

即在这n个w，s中满足w[i]<w[j]&&s[i]>s[j],要求:体重严格递增,速度严格递减,原始顺序不定

首先将s从大到小排序，即顺数固定后转化为最长上升子序列问题.

案例：

       6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 

Sample Output

       4 4 5 9 7 

1000 4000

1100 3000

2000 1900

8000 1400

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include 
            
             #include 
             
              #include
              
               #include
               
                using namespace std;#define INF 999999999#define eps 1e-4#define LL __int64#define maxn 26#define mol 1000000007#define N 505#define M 50010struct node{ int v,s,num;}p[1105];int pre[1105];//路径保存pre[i]表示 i 的前一个数int cmp(node a,node b){ return a.s>b.s;}void out(int k)//递归输出{ if(pre[k]==-1) { printf("%d\n",k); return; } out(pre[k]); printf("%d\n",k);}int main(){ int n=1,dp[1105]; while(~scanf("%d%d",&p[n].v,&p[n].s)) { p[n].num=n; n++; } sort(p+1,p+n+1,cmp); for(int i=1;i
                
                 p[i].s&&p[j].v
                 
                  maxx) { maxx=dp[j]; index=p[j].num; } } } dp[i]=maxx+1; pre[p[i].num]=index; if(dp[i]>ans) { ans=dp[i]; k=p[i].num; } } printf("%d\n",ans); out(k); return 0;}/*6008 13006000 2100500 20001000 40001100 30006000 20008000 14006000 12002000 1900*/