题解 | #拦截导弹#
拦截导弹
https://www.nowcoder.com/practice/dad3aa23d74b4aaea0749042bba2358a
此动态规划的状态转移方程为dp[i]=max{1, dp[j]+1 | j<i && A[j]>A[i]}.
#include<iostream>
using namespace std;
int height[26];
int dp[26];
int main(){
int k;
while(cin>>k){
for(int i=0;i<k;i++){
cin>>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[j]>=height[i]){
dp[i]=max(dp[j]+1,dp[i]);
}
}
answer=max(answer,dp[i]);
}
cout<<answer<<endl;
}
return 0;
}
