DP模板3

发表于 | 更新于: | 次
字数统计: 832 字 | 阅读时长 ≈ 3 分钟

我博客里的每一首歌都是精挑细选过的，个人至少循环了100+次，在这里分享

这首歌是2018年的6.18号，距离中考6天的时候找到的，中考前要放假一周嘛

那天晚上，我骑着自行车，听着这首歌，骑自行车来到了我现在在读的高中门前，站在大门口。看着晚自习的灯光，听着这首歌，幻想着高中的新生活，我还自嘲地和一起来的同学打赌，我肯定考不上这所高中

出录取分数线的那天，我们又约上了几个人一起骑车去另一个县城找小姐姐玩，骑到了半路，看到班主任发的录取分数线，我正好高了一分。当时高兴得大笑了起来，忘了一路上的疲劳，只顾骑着车往前冲

现在想起来，心里不由得生出了一丝喜悦，当然也夹杂着说不出的无奈，希望我能做到想做的事吧

⑧说了，又是一道动规入门题

你要问我为什么又是入门题？

还不是因为我太菜了？(QAQ

题目在这里

这题的难度是PJ / TG-难度

然而我花了二十分钟想第二问，还没想出来(菜爆了

贴代码，我相信如果你有心看我的DP入门系列看到这里的话，不难理解

这个写法是最容易理解的O(n²)方法，用树状数组可以优化到O(n log n),但是我不会写Orz

CCF原本的数据n²可以过，n log n应该是洛谷自己出的一些特殊数据，但可以作为进阶学习使用

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
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#include<stdlib.h>
#define FR(x,k,z) for(register int x = k; x <= z; x++)
#define FFR(x,k,z) for(register int x = k; x < z; x++)
typedef long long int64;

using namespace std;

int r = 1, dp[1616] = {}, tree[1616] = {};

int main()
{
	int maxx = 0, maxsys = 0, nows = 0, c = 1;
	char ch = 'a';
	while (scanf("%d%c", &c, &ch) == 2)//因为我太菜了所以只能这么读入数据，但好像也只能这样？
	{
		tree[r] = c;
		dp[r] = 1;
		r++;
		if (ch == '\n')
			break;
	}
	for (int i = r - 1; i >= 1; i--)//这里是第一问，具体分析看下面
	{
		for (int j = i + 1; j <= r; j++)
		{
			if (tree[i] >= tree[j])
			{
				dp[i] = max(dp[j] + 1, dp[i]) ;
			}
		}
		maxx = max(maxx, dp[i]);
		//printf("dp[%d] = %d\n", i, dp[i]);
	}
	for (int i = 1; i <= r; i++)//第二问，分析看下面
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (tree[i] > tree[j])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		maxsys = max(maxsys, dp[i]);
	}
	printf("%d\n%d", maxx, maxsys);
	return 0;
}

这题其实就算求一个最长下降序列和最长上升序列

为什么呢？

看题目可以知道，如果一枚导弹的高度高于之前那一枚，那么就拦截不到了，只能新开系统

如果高度低于前面那一枚，那么就可以继续用旧系统

所以这题其实就是求最长不上升序列和最长上升序列就完了

但是第二问我甚至没有想出来QAQ，看了眼题解才知道还能这样写

还有用树状数组的大佬Orz