2022年庐阳区青少年信息学科普日真题- 索道(way)
题目描述
山脚下有一个较为平坦的山路，共有N棵美人松，光头强打算利用这些美人松修建一条索道。这条索道中间高两头低，可以放弃一些美人松，但是光头强必须选择第K棵美人松作为索道的最高点。求建造这样的索道最多可以利用多少棵美人松。
输入格式
第一行两个正整数N和K。
第二行，N 个整数，表示从左往右各美人松的高度。
输出格式
一个整数，表示建造这样的索道利用美人松最大数。
输入输出样例
输入样例1：
10 6
1 3 2 4 2 5 6 3 4 1
输出样例1：
6
说明
N<=3000
提示说明
样例中，第6个数是5必选，作为最高点，可以选择 1 3 4 5 3 1。极端情况下，结果可能为1。
【解析】
1：这道题看成是两遍LIS问题即可，模板代码。
#include<bits/stdc++.h>
using namespace std;
int a[4000];
int dp[4000];
int main(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];dp[i]=1;}int ans=0;//计算第1~k棵树之间选择哪几棵树for(int i=1;i<=k;i++){for(int j=1;j<i;j++){if(a[j]<a[i]){dp[i]=max(dp[j]+1,dp[i]);}}}ans+=dp[k];dp[k]=1;//细节 //计算k~n之间选择哪几棵树，倒序看也是LIS问题 for(int i=n;i>=k;i--){
// dp[i]=1;for(int j=i+1;j<=n;j++){if(a[j]<a[i]){dp[i]=max(dp[i],dp[j]+1);}}}ans+=dp[k];cout<<ans-1;return 0;
}