刚开始输入写错了，最后还会接收一次值的
这道题如果只有一个维度，那么直接排序之后顺序输出就行了，但这里有二维，排序之后有一些点不能同时选，就需要决择了
先将所有老鼠按我们需要的大小关系排个序，然后就相当于求个最长上升子序列了
像这种第i个状态的值会和前面某数是什么有关系的，直接把前面的扫描一遍取最值就好了
感觉做dp的题，有两点很重要
一个是状态方程，，这是解题的关键
还有一个就是状态初始化，这是保证不会WA的关键
#include<stdio.h>#include<string>#include<math.h>#include<algorithm>const int inf=999999;using namespace std;int dp[1005];//第i个数的最长递增子序列长度的最大值 struct Mice{int w,s,pre,p;Mice(){}}a[1005];int cmp(Mice a,Mice b) {if(a.w!=b.w) return a.w<b.w;else return a.s>b.s;}void output(int post){if(a[post].pre==-1){printf("%d\n",a[post].p);return;}output(a[post].pre);printf("%d\n",a[post].p);}int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint n=1;a[0].w=0;a[0].s=inf;while(scanf("%d%d",&a[n].w,&a[n].s)!=EOF) n++;n–;//最后接收了一次空值for(int i=1;i<=n;i++) a[i].p=i;sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++) dp[i]=1;for(int i=1;i<=n;i++) a[i].pre=-1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[j].w<a[i].w&&a[j].s>a[i].s){if(dp[j]+1>dp[i]) {dp[i]=dp[j]+1;a[i].pre=j;}}}}//for(int i=1;i<=n;i++) printf("%d %d\n",a[i].w,a[i].s);int ma=0,post;for(int i=1;i<=n;i++){if(dp[i]>ma){ma=dp[i];post=i;}}printf("%d\n",dp[post]);output(post);}
鸟儿爱美，不仅需要羽毛之美，还需要鸣声婉转之美;
