dp求順序hdu1160

題意是隻求一次的順序，先按照速度從大到小排序，速度想等到按體重增序排列。

然後基本就變成了求已定順序序列的最長遞增序列遞增，跟那個求一緻最大序列和的基本一緻。

dp【i】裡存儲的是到目前i最大的遞增序列個數最大的數。

dp[i+1]就是在a【i+1】大于前面的a【j】的情況下，dp【i+1】=dp【j】+1;

輸出的就是從最大的dp【】值從後往前輸出，是以用了個棧改成從前往後。

以為題意隻輸出一個正确序列就好。

思路是從開始的結構體排序，打一打就想出來的，bug，調了一天，确定dp【】最大值得時候和

需要記錄角标，開始就弄混了，這個bug也是通過出資料找出來的。

第一次交沒有輸出序列個數，wa了2次。

#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
stack<int > s;

struct mice
{
    int x,y,z;
    bool operator < (const mice&b ) const{

        if(y==b.y) return x<b.x;
        return y>b.y;
    }
}a[1010];
int dp[1010];
int main()
{
    int i=0;
    while(scanf("%d%d",&a[i].x,&a[i].y)!=EOF) {  a[i].z=i+1; i++; }
//    printf("\n");

//    printf("i==%d\n",i);

    sort(a,a+i);


//    for(int j=0;j<i;j++) printf("%d  %d  %d\n",a[j].x,a[j].y,a[j].z);

    int maxx = 0,maxIndex=0;

    for(int j=0;j<i;j++)
    for(int k=0;k<j;k++){
        if(a[k].x<a[j].x ) dp[j]=max(dp[k]+1,dp[j]);
        if(dp[j]>maxx) { maxx = dp[j]; maxIndex = j; }

    }
//    printf("maxx==%d\n",maxx);

//    for(int j=0;j<i;j++) printf("%d  ",dp[j]);
//    printf("\n");


//    printf("%d\n",a[maxx].z);
//    printf("%d\n",dp[maxx]+1);
    s.push(a[maxIndex].z);
        printf("%d\n",dp[maxIndex]+1);
//        printf("%d\n",a[maxIndex].z);
    dp[maxIndex]-=1;
    for(int k=maxIndex-1;k>=0;k--){

        if(dp[k]==dp[maxIndex]){
//                printf("%d\n",dp[k]);
//            printf("%d\n",a[k].z);

            s.push(a[k].z);
            dp[maxIndex]-=1;
        }
    }

    while(!s.empty()){
        printf("%d\n",s.top());
        s.pop();
    }




    return 0;
}
/**
1 5
1 3
2 4
2 2
3 3
4 4
1 3
4 2
5 1
^Z

1  5  1
2  4  3
4  4  6
1  3  2
1  3  7
3  3  5
2  2  4
4  2  8
5  1  9
0  1  2  0  0  2  1  3  4
4
5
3
1
*/
/**
1 5
1 3
2 4
2 2
3 3
4 4
1 3
4 2
5 1
^Z

1  5  1
2  4  2
3  3  3
4  2  4
5  1  5
0  1  2  3  4
5
1
2
3
4
5

*/