Codeforces Problem-580A Kefa and First Steps

Codeforces Problem-580A Kefa and First Steps Codeforces Problem-580A Kefa and First Steps

基本思想：

  作为一个A题，其实没有必要考虑它的核心算法，能用暴力做出来是最直接的；但是现在做题不是用来刷数量的，而是找到不同的方法，以掌握算法为主。这道题的标签是dp，那就用dp的思想做一下。这里的dp[i]是指第i个元素之前，最长非递减子序列的长度，即dp[0]=1，后面的每一个元素都与前一个元素进行比较，如果大于或者等于前一个元素，dp[i]=dp[i-1]+1；否则，dp[i]=1。最后再找出dp数组的最大值即可。

AC代码：

#include 
using namespace std;

int main()
{
	int n;
	int a[100005];
	int dp[100005];
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
	cin>>n;
	for (int i=0;i>a[i];
	dp[0]=1;
	int ans=0;
	for (int i=1;i=a[i-1])
			dp[i]=dp[i-1]+1;
		else
			dp[i]=1;
	}
	cout<<*max_element(dp,dp+n)<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5504207.html