题解 | #拦截导弹#

拦截导弹

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;
}


全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
05-20 21:57
已编辑
门头沟学院 Java
喜欢吃卤蛋的悲伤蛙在...:建信融通没消息吧,我2说有实习挂简历不理了
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务