今天第一次知道原来sort的速度快过选排,而这道题简单的动规题,体重先升序,如果体重相等,则速度快的优先,而用count【1200】【2】,记录每个小鼠前有几个满足条件的,用count【i】【1】记录在该小鼠前满足条件的小鼠序号,最后记录最后的小鼠序号max,而conut后搜出最长序列,倒叙打出。
#include<iostream>
#include<algorithm>
using namespace std;
struct st
{ int w;
int s;
int num;
};
bool cmp(struct st a,struct st b)
{ if(a.w!=b.w) return a.w<b.w;
return a.s>b.s;
}
int main()
{ struct st a[1200];int t=0;
while(cin>>a[t].w>>a[t].s)
{ a[t].num=t+1;
t++;
}
sort(a,a+t,cmp);
int count[1200][2];
memset(count,0,sizeof(count));
count[0][0]=1;count[0][1]=0;
int max=0,result=1;//找出最长的序列并记录每只小鼠前满足条件的小鼠序号
for(int i=1;i<t;i++)
{ count[i][0]=1;
count[i][1]=i;
for(int k=0;k<i;k++)
{ if(a[i].s<a[k].s&&a[i].w>a[k].w)
if(count[i][0]<count[k][0]+1)
{ count[i][0]=count[k][0]+1;
count[i][1]=k;
if(result<=count[i][0])
{ result=count[i][0];
max=i;
}
}
}
}
cout<<result<<endl;
if(result==1)
cout<<a[max].num<<endl;
else //找到最长的序列数。
{
int b[1200],k=0;
b[k++]=max;
while(count[b[k-1]][1]!=b[k-1])
b[k++]=count[b[k-1]][1];
for(int i=k-1;i>=0;i--)
cout<<a[b[i]].num<<endl;
}
return 0;
}