首页 > 代码库 > [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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。