首页 > 代码库 > [luoguP1410] 子序列(DP)

[luoguP1410] 子序列(DP)

传送门

 

发现一个结论。

只要存在长度>=3的非严格下降子序列就是NO,反之就是YES

 

#include <cstdio>#include <iostream>#define N 2001#define max(x, y) ((x) > (y) ? (x) : (y))int n, tmp;int a[N], f[N];inline int read(){	int x = 0, f = 1;	char ch = getchar();	for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;	return x * f;}int main(){	int i, j;	while(~scanf("%d", &n))	{		for(i = 1; i <= n; i++) a[i] = read();		for(i = 1; i <= n; i++)		{			tmp = 0;			for(j = i - 1; j >= 1; j--)				if(a[j] >= a[i])					tmp = max(tmp, f[j]);			f[i] = tmp + 1;			if(f[i] >= 3)			{				puts("No!");				break;			}			}		if(i > n) puts("Yes!");	}	return 0;}

  

[luoguP1410] 子序列(DP)