题意是只求一次的顺序,先按照速度从大到小排序,速度想等到按体重增序排列。
然后基本就变成了求已定顺序序列的最长递增序列递增,跟那个求一致最大序列和的基本一致。
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
*/