HDU 1160 FatMouse's Speed(LIS)

// // main.cpp // Richard // // Created by 邵金杰 on 16/9/15. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxn=1000+10; int dp[maxn],f[maxn]; struct node{ int w,s,index; }p[maxn]; int cmp(node &a,node &b){ if(a.w!=b.w) return a.w<b.w; return a.s>b.s; } int main() { int k=1; while(scanf("%d%d",&p[k].w,&p[k].s)!=EOF) {dp[k]=1;p[k].index=k;k++;} sort(p+1,p+k,cmp); int len=0,pos=-1; memset(f,-1,sizeof(f)); for(int i=1;i<k;i++) { for(int j=1;j<i;j++) { if(p[i].w>p[j].w&&p[i].s<p[j].s&&dp[j]+1>dp[i]){//dp[j]+1>dp[i]一定要判断，否则f会指错 dp[i]=max(dp[i],dp[j]+1); f[i]=j; if(dp[i]>len){ len=dp[i];pos=i; } } } } int s[maxn]; int x=0; if(len==0) printf("1\n1\n"); else printf("%d\n",len); while(pos!=-1) { s[x++]=p[pos].index; pos=f[pos]; } for(int i=x-1;i>=0;i--) printf("%d\n",s[i]); }