牛客 12.4. 拦截导弹
原题链接
简单
作者:
Chi
,
2022-07-05 11:09:44
,
所有人可见
,
阅读 206
王道机试指南 动态规划 最长递增子序列
(动态规划) $O(n^2)$
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 25;
int height[MAXN];
int dp[MAXN];
int main(){
int k;
while(scanf("%d",&k) != EOF){
for(int i = 0 ; i < k;i++){
scanf("%d",&height[i]);
}
int answer = 0;
for(int i = 0;i<k;i++){
dp[i]=1; //初始化为1
for(int j = 0 ;j < i ; j++)
if(height[i]<=height[j])//最长不增子序列条件
{
dp[i]=max(dp[i],dp[j]+1);
}
answer = max(dp[i],answer);//每次遍历完Ai之前的Aj后更新
}
cout<<answer<<endl;
}
return 0;
}