主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
题解：P1410 子序列
最后更新于 2025-06-15 21:12:59
作者
Fire_Kylin
分类
题解
题解
P1410
复制 Markdown
查看原文
更新内容
# 思路 其实这一道题可以利用一个小结论： **如果出现最长下降子序列长度超过 2 的，一定不能分成两个严格递增的子序列。** 其实这一个小结论的证明方法很简单，就是小学学过的**鸽巢原理（即抽屉原理）**。这个原理告诉我们 **3 个下降的数字，放到两个盒子之中一定会有一个盒子是一定下降。** ~~虽然听起来有点绕哈，但多读几遍就看懂了。~~ # 实现 由上面的小结论可以知道，我们只需要统计最长下降子序列的长度，判断其是否小于等于 $2$ 就行了。 最长下降子序列我就不赘述了，毕竟你都来做蓝题了不可能还不会这个。 # ACcode ~~跟之前的码风不太一样哈。~~ ```cpp #include <bits/stdc++.h> using namespace std; int c[2008], f[2008], n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); while(cin >> n) { memset(f, 0, sizeof(f)); int ans = 0; for (int i = 1 ; i <= n ; i++) cin >> c[i]; for (int i = 1 ; i <= n ; i++) { f[i] = 1; for (int j = 1 ; j < i ; j++) if (c[i] <= c[j]) f[i] = max(f[i], f[j] + 1); ans = max(ans, f[i]); } if (ans <= 2) cout << "Yes!\n"; else cout << "No!\n"; } return 0; } ```
正在渲染内容...
点赞
3
收藏
0
