题意:要求找到的体重递增,速度递减的老鼠,并且输出最长的长度数,而且输出各自的序列数。Special Judge
思路:先按体重由小到大排序,再找最长速度递减序列。
转移方程:mou[i].w>mou[j].w&&mou[i].s<mou[j].s&&dp[j]+1>dp[i]
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define clc(a,b) sizeof(a,b,sizeof(a))
#define LL long long
#include<cmath>
using namespace std;
int dp[];//表示以i结尾的最长长度
int rightt[];//最终输出序列
int pre[];//记录i的前驱是什么
struct node {
int w,s,index;
} mou[]; bool cmp(node a,node b) {
if(a.w!=b.w) return a.w<b.w;
else return a.s>b.s;
} int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int k=;
while(scanf("%d%d",&mou[k].w,&mou[k].s)!=EOF) {
mou[k].index=k;
k++;
}
sort(mou+,mou+k,cmp);
clc(dp,);
clc(rightt,);
clc(pre,);
int tot=;
int last;
for(int i=; i<k; i++) {
for(int j=; j<i; j++) {
if(mou[i].w>mou[j].w&&mou[i].s<mou[j].s&&dp[j]+>dp[i]) {
dp[i]=dp[j]+;
pre[i]=j;
if(tot<dp[i]) {
tot=dp[i];
last=i;
}
}
}
}
int r=last;
int i=;
while(r!=) {
rightt[i++]=r;
r=pre[r];
}
printf("%d\n",i);
for(int j=i-; j>=; j--) {
printf("%d\n",mou[rightt[j]].index);
}
return ;
}