阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第8节：动态规划

第1题【NOIP】2013

#include <iostream>
using namespace std;
int main() {
04	const int SIZE = 100;
	int height[SIZE], num[SIZE], n, ans;
06	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &height[i]);
		num[i] = 1;
		for (int j = 0; j < i; j++) {
11			if ((height[j] < height[i]) && (num[j] >= num[i]))
				num[i] = num[j]+1;
		}
	}
	ans = 0;
	for (int i = 0; i < n; i++) {
		if (num[i] > ans) ans = num[i];
	}
	printf("%d\n", ans);
	return 0;
}

●判断题

(1)将第4行的程序移动到第2、3行中间，程序能够正常运行

{{ select(1-1) }}

• 正确
• 错误

(2)第6行输入n=5,则输出ans的值一定小于5

{{ select(1-2) }}

• 正确
• 错误

(3)把01行的iostream改为cstdio时不会编译错误。

{{ select(1-3) }}

• 正确
• 错误

(4)如果输出是1,则height数组中的数一定是递减的。

{{ select(1-4) }}

• 正确
• 错误

●选择题

(5)当n=6时，输入height数组为2 5 3 11 12 4,输出为.。

{{ select(1-5) }}

• 4
• 2
• 14
• 6

《6)如果将第11行的height[j]<height[i]改成height[j]>height[i],则第(5)题的输出结果为( )。。

{{ select(1-6) }}

• 4
• 2
• 14
• 6

第2题【NOIP】2016

#include <iostream>
using namespace std;
int lps(string seq, int i, int j) {
	int len1, len2;
	if (i == j)
		return 1;
7	if (i > j)
8		return 0;
	if (seq[i] == seq[j])
		return lps(seq, i + 1, j - 1) + 2;
	len1 = lps(seq, i, j - 1);
	len2 = lps(seq, i + 1, j);
	if (len1 > len2)
		return len1;
	return len2;
}
int main() {
	string seq = "acmerandacm";
	int n = seq.size();
	cout << lps(seq, 0, n - 1) << endl;
	return 0;
}

●判断题

(1)n代表seq的长度。

{{ select(2-1) }}

• 正确
• 错误

(2)输 入acmerandacm,输出5

{{ select(2-2) }}

• 正确
• 错误

(3)第7～8行代码删去后程序仍能正常运行。

{{ select(2-3) }}

• 正确
• 错误

(4)程序最好情况下的时间复杂度为O($n^2$)。

{{ select(2-4) }}

• 正确
• 错误

●选择题

(5)程序的最坏时间复杂度为( )

{{ select(2-5) }}

• O(nlogn)
• O($n^2$)
• O(n)
• O($2^n$)

(6)函数lps(seq,i,j)用途是( )。

{{ select(2-6) }}

• 求字符串seq的最长回文子序列长度。
• 求字符串seq中区间[i,j]上的最长回文子串长度。
• 求字符串seq中区间[i,j]上的最长回文子序列长度。
• 求字符串seq中区间[i,j]上的最长相同前缀后缀长度。