索道（way）

庐阳区2022年信息学竞赛试题

题目描述 Description

山脚下有一个较为平坦的山路，共有N棵美人松，光头强打算利用这些美人松修建一条索道。这条索道中间高两头低，可以放弃一些美人松，但是光头强必须选择第K棵美人松作为索道的最高点。求建造这样的索道最多可以利用多少棵美人松。

输入描述 Input Description

第一行两个正整数N和K。

第二行，N 个整数，表示从左到右各美人松的高度。

输出描述 Output Description

一个整数，表示建造这样的索道利用美人松最大数。

样例输入 Sample Input

10 61 3 2 4 2 5 6 3 4 1

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

数据范围

N<=3000

提示说明

样例中，第6个数是5必选，作为最高点，可以选择1 3 4 5 3 1，极端情况下，结果可能为1。

上代码：

#include
using namespace std;
int n, k;
int a[3005];
int f[3005], g[3005];
int main() {cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= k; i++) {f[i] = 1;for (int j = 1; j < i; j++) {if (a[j] < a[i]) {f[i] = max(f[i], f[j] + 1);}}}for (int i = n; i >= k; i--) {g[i] = 1;for (int j = n; j > i; j--) {if (a[j]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！