题解：P1410 子序列

Fire_Kylin · 2025-05-27 22:19:42 · 题解

思路

其实这一道题可以利用一个小结论：

如果出现最长下降子序列长度超过 2 的，一定不能分成两个严格递增的子序列。

其实这一个小结论的证明方法很简单，就是小学学过的鸽巢原理（即抽屉原理）。这个原理告诉我们 3 个下降的数字，放到两个盒子之中一定会有一个盒子是一定下降。

虽然听起来有点绕哈，但多读几遍就看懂了。

实现

由上面的小结论可以知道，我们只需要统计最长下降子序列的长度，判断其是否小于等于 2 就行了。

最长下降子序列我就不赘述了，毕竟你都来做蓝题了不可能还不会这个。

ACcode

跟之前的码风不太一样哈。

#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;
}