题解 | #拦截导弹#

拦截导弹

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-07 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-04 15:20
牛客61197583...:看到室友一个个没怎么学通过关系直接入职或者接到面试,真的很难受。八股不知道背了多少遍,hot100也刷了1.5遍了,但就是没有面试的机会,唉
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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