HDU-FatMouse's Speed

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int MAX = 1001; struct S{ int a,b,t; }s[MAX]; int dp[MAX],path[MAX],over[MAX]; bool cmp(struct S a,struct S b){ if(a.a!=b.a) return a.a<b.a; else return a.b>b.b; } int main(){ int n=0; while(~scanf("%d%d",&s[n].a,&s[n].b)){ s[n].t=n+1; n++; } sort(s,s+n,cmp); int max1 = 0,index=0; if(n==0){ printf("0\n0\n"); return 0; } for(int i=0;i<n;i++){ dp[i] = 1; for(int j=0;j<i;j++){ if(s[i].a>s[j].a&&s[i].b<s[j].b){ // dp[i] = max(dp[i],dp[j]+1); // path[i] = j; /*上面注释是错的 一定要在这条件下，才改变path[i]=j 因为path记录的是它上一个(他爸)的下标， 必须是满足个数最多的那个(不是哪个都是他爸) */ if(dp[i]<dp[j]+1){ dp[i] = dp[j]+1; path[i] = j; } } } if(dp[i]>max1){ max1 = dp[i]; index = i; } } printf("%d\n",max1); for(int i=max1-1;i>=0;i--){ over[i] = s[index].t; index = path[index]; } for(int i=0;i<max1;i++){ printf("%d\n",over[i]); } return 0; }