【四】【算法】P1020 [NOIP1999 提高组] 导弹拦截,Dilworth 定理 推论,最长递增子序列长度,最长非递增子序列长度,最少递增子序列个数,最少非递增子序列个数,

    #include<bits/stdc++.h>
    using namespace std;
    vector<int> a;
    vector<int>dp_rise;
    vector<int>dp_decline;
    /*
    代码逻辑没有问题, 但是时间复杂度太大了!
    最长非上升和最长上升的区别
    前者包括等于,后者严格递增
    */
    #if 0 
    int main() {
    	int nums;
    	while (cin >> nums) {
    		a.push_back(nums);
    	}
    	int n = a.size();
    	dp_rise.resize(n, 1);
    	dp_decline.resize(n, 1);
    
    
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < i; j++) {
    			if (a[j] < a[i]) {
    				dp_rise[i] = max(dp_rise[j] + 1, dp_rise[i]);
    			} else if (a[j] >= a[i]) {
    				dp_decline[i] = max(dp_decline[j] + 1, dp_decline[i]);
    			}
    		}
    	}
    
    	int max_rise = *max_element(dp_rise.begin(), dp_rise.end());
    	int max_decline = *max_element(dp_decline.begin(), dp_decline.end());
    
    	cout << max_decline << " " << max_rise << endl;
    
    
    }
    #endif
    /*
    利用Dilworth 定理解决最长上升非上升子序列,最长下降非下降子序列和最少子序列个数问题
    最长非上升子序列的长度 等价于 最少的上升子序列划分的个数
    最长上升子序列的长度 等价于 最少的非上升子序列划分的个数
    下降同理,而我们计算 最少的上升子序列划分的个数 或者 最少的非上升子序列划分的个数 更加容易
    
    目标:非上升长度和非上升个数
    等价于 上升个数和非上升个数
    >   <=
    */
    #if 1
    int main() {
    	int nums;
    	while (cin >> nums) {
    		a.push_back(nums);
    	}
    	int n = a.size();
    	//rise 非上升序列长度<=>最少上升序列个数 >  1 2 3 4 3 4 5 2 3 4 存储的是严格递增最后一个数字
    	//decline 最少非上升序列个数 <=    4 3 2 2 4 3 2 2
    
    	for (int i = 0; i < n; i++) {
    		auto it = upper_bound(dp_rise.begin(), dp_rise.end(), a[i],greater<int>());//<
    		auto it2 = lower_bound(dp_decline.begin(), dp_decline.end(), a[i]);//>=
    		if (it == dp_rise.end()) {
    			dp_rise.push_back(a[i]);
    		} else {
    			*it = a[i];
    		}
    
    		if (it2 == dp_decline.end()) {
    			dp_decline.push_back(a[i]);
    		} else {
    			*it2 = a[i];
    		}
    	}
    
    	cout << dp_rise.size() << " " << dp_decline.size() << endl;
    
    	
    }
    #endif
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-07-13/aPL0jbDs6EeFlySGQJK2v3R4nmVp.png)

    int main() {
    int nums;
    
    // 读取输入直到输入结束
    while (cin >> nums) {
        a.push_back(nums); // 将每个数字加入序列
    }
    
    int n = a.size(); // 获取序列的大小
    
    // 初始化 dp 数组，所有元素初始值为 1，因为每个元素自身也可以作为一个长度为 1 的子序列
    dp_rise.resize(n, 1);    // 最长上升子序列的长度数组
    dp_decline.resize(n, 1); // 最长下降子序列的长度数组
    
    // 双重循环来计算 dp 数组
    for (int i = 0; i < n; i++) {
        // 对于每个 a[i]，检查它前面的所有元素 a[j]
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                // 如果 a[j] < a[i]，说明 a[i] 可以接在 a[j] 之后，形成一个更长的上升子序列
                dp_rise[i] = max(dp_rise[j] + 1, dp_rise[i]);
            } else if (a[j] >= a[i]) {
                // 如果 a[j] >= a[i]，说明 a[i] 可以接在 a[j] 之后，形成一个更长的下降子序列
                dp_decline[i] = max(dp_decline[j] + 1, dp_decline[i]);
            }
        }
    }
    
    // 找到 dp_rise 和 dp_decline 中的最大值
    int max_rise = *max_element(dp_rise.begin(), dp_rise.end());         // 最长上升子序列的长度
    int max_decline = *max_element(dp_decline.begin(), dp_decline.end()); // 最长下降子序列的长度
    
    // 输出结果，先输出最长下降子序列的长度，再输出最长上升子序列的长度
    cout << max_decline << " " << max_rise << endl;
    
    return 0;
    }
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-07-13/quaWmRwkJ7pdg1xiSTeIcULY6VbF.png)

    iterator upper_bound(iterator first, iterator last, const T& value);

    
    iterator upper_bound(iterator first, iterator last, const T& value, Compare comp);
    
    auto it = upper_bound(dp_rise.begin(), dp_rise.end(), a[i], greater<int>());
    //找严格小于
    
    
    cpp

    iterator lower_bound(iterator first, iterator last, const T& value);

    
    iterator lower_bound(iterator first, iterator last, const T& value, Compare comp);
    
    auto it = lower_bound(v.begin(), v.end(), a[i], greater<int>());
    //找小于等于
    
    
    cpp