蓝桥杯--算法提高天天向上（Java）

98 阅读 0 评论 65 点赞

我是靠谱客的博主怕黑小霸王，这篇文章主要介绍蓝桥杯--算法提高天天向上（Java），现在分享给大家，希望可以做个参考。

【资源限制】
时间限制：1.0s 内存限制：256.0MB
【问题描述】
　　A同学的学习成绩十分不稳定，于是老师对他说：“只要你连续4天成绩有进步，那我就奖励给你一朵小红花。”可是这对于A同学太困难了。于是，老师对他放宽了要求：“只要你有4天成绩是递增的，我就奖励你一朵小红花。”即只要对于第i、j、k、l四天，满足i<j<k<l并且对于成绩wi<wj<wk<wl，那么就可以得到一朵小红花的奖励。现让你求出，A同学可以得到多少朵小红花。
【输入格式】
　　第一行一个整数n，表示总共有n天。第二行n个数，表示每天的成绩wi。
【输出格式】
　　一个数，表示总共可以得到多少朵小红花。
【样例输入】
6
1 3 2 3 4 5
【样例输出】
6
数据规模和约定
　　对于40%的数据，n<=50；
　　对于100%的数据，n<=2000，0<=wi<=10⁹。

————————————————————————————————————————————————————
参考原文

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;

public class Main {
	static int[] w;
	//dp[i][j] 定义为以w[i]为起点，所有递增序列长度为j的序列的个数。
	static long[][] dp = new long[2001][5];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		w = new int[n + 1];
		for (int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
		}
		//dp[i][j]= ∑dp[k][j-1] (k>i,a[k]>a[i])
		//1 3 2 3 4 5
		for (int i = n - 1; i >= 0; i--) {//因为dp[n-1][1]是显然的，所以从后往前递推
			dp[i][1] = 1;
			//w[i]是当前序列的头
			for (int j = i + 1; j < n; j++) {//w[j]是第二，对应后面的dp[j][k-1]
				if (w[j] > w[i]) {
				//k可以理解为当前递增序列的长度
					int k = 2;//此时序列长度至少为2，所以初始k=2
					while (k <= 4) {
						if (dp[j][k - 1] == 0) break;//防止while死循环
		//以w[i]为首，长度为k的递增序列的个数 包含 以w[j]为首，长度为k-1的递增序列的个数
						dp[i][k] += dp[j][k - 1];
						k++;//下次while求解以w[i]为首，长度为k++的递增序列的个数
					}
				}
			}
		}
		long res = 0;
		for (int i = n - 1; i >= 0; i--) {
			res += dp[i][4];
		}
		System.out.println(res);
	}
}