10131越大越聪明（蓝桥杯每周一题）
[问题描述]
一些人认为，大象的体型越大，脑子越聪明。为了反驳这一错误观点，你想要分析一组大象的数据，找出尽量
多的大象组成一个体重严格递增但 IQ 严格递减的序列。
[输入]
输入包含若干大象的数据，每行一头大象，直到输入结束。每头大象的数据包括两个整数：第一个是以千克为
单位的体重，第二个是以整百为单位的 IQ 指数。两个整数均在 1 到 10000之间。输入最多包含 1000 头
大象。两头大象可能有相同的体重，或者相同的 IQ，甚至体重和 IQ 都相同。
[输出]
输出第一行应当包括一个整数 n，为找到的大象序列的长度。接下来的 n 行，每行包含一个正整数，表示一
头大象。用 W[i] 和 S[i] 表示输入数据中第 i 行的两个数，则若找到的这一序列为 a[1]，a[2]，
… ，a[n]，则必须有：
W [a[1]] < W [a[2]] < … < W [a[n]] 和 S[a[1]] > S[a[2]] > … > S[a[n]]i
这里的 n 应当是最大可能值。所有不等关系均为严格不相等：体重严格递增，而 IQ 严格递减。
如果存在多组解，你的程序只需输出任何一个解。
[样例输入]
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
[样例输出]
4
4
5
9
7
解释：符合题意的最长序列长度为4，按顺序是
第4行 1000 4000
第5行 1100 3000
第9行 2000 1900
第7行 8000 1400
欢迎评论，~~滑稽
import java.util.Scanner;
public class Demo102 {
static int []w = new int[1000];
static int []s = new int[1000];
static int n = 9;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 1; i <=9; i++)
{
w[i]=sc.nextInt();
s[i]=sc.nextInt();
}
int[] d = new int [1000];
d[9] = 1;
//dp的初始值设置的最后一位
//这里是把i从后向前
//其实我的dp数组是从前向后的，
//最后更新的就是从i=1，然后j》1《=n证明是整个数组
//这里如果把i从前向后，j就要从后向前，并且后面输出就需要从后向前 很烦
for (int i = n - 1; i >= 1; i--){
d[i] = 1;
for (int j = i + 1; j <= n; j++){
if (w[i]<w[j] && s[i]>s[j])
if (d[i] < d[j] + 1)
d[i] = d[j] + 1;
}
}
//find max
int start = 1;
for (int i = 2; i <= n; i++)
if (d[i] > d[start])start = i;
System.out.println(d[start]);
System.out.println(start);
for (int i = 1; i <=n;i++)
//这里在不断的让节点替换，也就是上面dp过程时候的逆推
if (w[start]<w[i] && s[start]>s[i] && d[start] == d[i] + 1)
{
System.out.println(i);
start = i;
}
}
}
