思路:
第一个问题很好解决,就是最长不上升子序列,利用贪心 + 二分的dp就可以解决,这里给一个二分查找的函数
二分查找
第二个问题是问给出的序列最少可以分成几个不上升子序列,其实这里有一个定理
由Dilworth 定理,不上升子序列的最小划分数为 a 的最长上升子序列长度。
所以第二个问题就转化为了求这个序列的最长上升子序列,其实如果要省事的话,可以把这个序列颠倒过来,然后就转化为第一个问题
code
#include <bits/stdc++.h> using namespace std; const int maxn = 100000 + 5; int dp[maxn],a[maxn]; int n = 1; void Solve() { memset(dp, 0, sizeof dp); //先求最长不上升子序列 int ans= 1; dp[ans] = a[1]; for(int i = 2; i <= n; i++){ if(a[i] <= dp[ans]) dp[++ans] = a[i]; else{ //找到第一个小于等于a[i]的数字 int idx = lower_bound(dp + 1, dp + ans, a[i],greater<int>()) - dp; dp[idx] = a[i]; } } cout<<ans<<endl; } int main() { while(cin>>a[n]) n++; n--; Solve(); //由Dilworth}Dilworth 定理,不上升子序列的最小划分数为 a 的最长上升子序列长度。 reverse(a + 1, a + n + 1); Solve(); return 0; }