• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【解题报告】洛谷P1410 子序列

开发技术 开发技术 6小时前 1次浏览

【解题报告】洛谷P1410 子序列

题目链接

https://www.luogu.com.cn/problem/P1410

思路

我们考虑动态规划

(f[i]) 表示到 (i) 的最长的递减的长度

发现,如果 (f[i])​ 大于 (2) 的话,这个序列就不成立

反之,这个序列成立

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n;
int main()
{
	while(cin>>n)
	{
		int a[2005],f[2005];
		bool flag=false;
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			f[i]=1; 
			for(int j=i-1;j>=0;j--)
			{
				if(a[i]<a[j])
				f[i]=max(f[i],f[j]+1);
			}
			if(f[i]>2)
				flag=true;
		}
		if(flag)
			cout<<"No!"<<'n';
		else
			cout<<"Yes!"<<'n';
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:【解题报告】洛谷P1410 子序列
喜欢 (0)