Java实现UVA10131越大越聪明(蓝桥杯每周一题)

时间:2023-12-16 23:36:14

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;
} }
}