动态规划是算法学习中的核心内容，本文通过三个经典问题，逐步深入理解最长上升子序列（LIS）及其变体。

1. 基础LIS问题：B3637

给定一个序列，求出其中最长的严格递增子序列的长度。基本思路是定义dp[i]表示以第i个元素结尾的最长上升子序列长度，通过遍历前面所有元素，若a[j] < a[i]，则更新dp[i] = max(dp[i], dp[j] + 1)。

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1009;
long long arr[MAX], dp[MAX];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = 1;
        for(int j = 0; j < i; j++) {
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i < n; i++) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}

2. 老鼠体重与速度问题

给定老鼠的体重和速度数据，要求找出最大子集，使得体重严格递增且速度严格递减。处理方式是先对结构体排序：按体重升序，若体重相同则按速度降序。排序后，问题转化为在速度序列中找最长下降子序列，注意体重相等的情况不能计入。

#include<iostream>
#include<algorithm> 
const int SIZE = 100010;
using namespace std;
struct Mouse {
    int weight;
    int speed;
} mice[SIZE];
int dp[SIZE], n, total;

bool compare(Mouse x, Mouse y) {
    if(x.weight != y.weight) return x.weight < y.weight;
    return x.speed > y.speed;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> mice[i].weight >> mice[i].speed;
    }
    sort(mice, mice + n, compare);
    
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++) {
            if(mice[i].speed < mice[j].speed && mice[i].weight != mice[j].weight) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int result = 0;
    for(int i = 0; i < n; i++) result = max(result, dp[i]);
    cout << result << endl;
    return 0;
}

3. P1020 导弹拦截系统

问题描述：导弹拦截系统每次拦截的导弹高度不能高于前一次，给定导弹序列，求最多能拦截多少导弹（即最长不升子序列长度），以及全部拦截所需最少系统数。核心技巧：最少系统数等于最长上升子序列的长度（Dilworth定理）。因此问题简化为同时计算最长不升子序列和最长上升子序列。

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
int heights[MAXN], dp_inc[MAXN], dp_dec[MAXN];

int main() {
    int idx = 0;
    while(scanf("%d", &heights[idx]) != EOF) {
        dp_inc[idx] = 1;
        dp_dec[idx] = 1;
        idx++;
    }
    for(int i = 0; i < idx; i++) {
        for(int j = 0; j < i; j++) {
            if(heights[i] > heights[j]) {
                dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1);
            }
            if(heights[i] <= heights[j]) {
                dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1);
            }
        }
    }
    int max_len = 0, min_sys = 0;
    for(int t = 0; t < idx; t++) {
        max_len = max(max_len, dp_dec[t]);
        min_sys = max(min_sys, dp_inc[t]);
    }
    cout << max_len << endl << min_sys << endl;
    return 0;
}