关于动态规划，这里有我的一些观点：

1. both我&文晶目前（编者注：2025年4月23日）还没学动态规划；

2. 动态规划看不懂；

3. 但是可E的文晶竟然上个补习班就做了几道dp

这是文晶做的一道题：拦截导弹

太坏了，我堂堂LZH竟然看不懂鸡爪（即文晶）的代码，看了半天只觉得有点二分查找（可是both I and wwenjing还没学）的代码：

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int a[N], d[N], len, h, n;
int main()
{
	while(cin >> h)
		a[++n] = h;
	d[++len] = a[1];
	for(int i = 2; i <= n; ++i)
	{
	    if(a[i] <= d[len])
            d[++len] = a[i];
	    else
	    {
	        int l = 1, r = len, m;
	        while(l < r)
	        {
	            m = (l+r)/2;
	            if(d[m] < a[i])
	               r = m;
	            else
	               l = m+1;
            }
            d[l] = a[i];
        }
    }
    cout << len << endl;
    len = 0;
    d[++len] = a[1];
	for(int i = 2; i <= n; ++i)
	{
	    if(a[i] > d[len])
	        d[++len] = a[i];
	    else
	    {
            int l = 1, r = len, m;
            while(l < r)
            {
                m = (l+r)/2;
                if(d[m] >= a[i])
                    r = m;
                else
                    l = m+1;
            }
            d[l] = a[i];
        }
	}
	cout << len << endl;
	return 0;
}

感谢DeepSeek的讲解。。。

代码功能分析

这段代码实现了导弹拦截问题的两个关键计算：

1. 第一行输出：最多能拦截的导弹数量（最长不上升子序列长度）
2. 第二行输出：拦截所有导弹最少需要的系统数量（等于最长严格上升子序列长度）

代码详解

1. 输入处理

while(cin >> h)
 a[++n] = h;

• 读取所有输入的导弹高度，存储在数组 a 中
• n 记录导弹的总数量

2. 计算最长不上升子序列（第一问）

d[++len] = a[1];
for(int i = 2; i <= n; ++i)
{
   if(a[i] <= d[len])
       d[++len] = a[i];
   else
   {
       int l = 1, r = len, m;
       while(l < r)
       {
           m = (l+r)/2;
           if(d[m] < a[i])
               r = m;
           else
               l = m+1;
       }
       d[l] = a[i];
   }
}
cout << len << endl;

• 使用贪心+二分法优化计算最长不上升子序列
• d 数组维护当前可能的子序列
• 当新导弹高度 ≤ d 数组末尾时，直接扩展序列
• 否则，二分查找合适位置进行替换

3. 计算最长严格上升子序列（第二问）

len = 0;
d[++len] = a[1];
for(int i = 2; i <= n; ++i)
{
   if(a[i] > d[len])
       d[++len] = a[i];
   else
   {
       int l = 1, r = len, m;
       while(l < r)
       {
           m = (l+r)/2;
           if(d[m] >= a[i])
               r = m;
           else
               l = m+1;
       }
       d[l] = a[i];
   }
}
cout << len << endl;

• 同样使用贪心+二分法，但改为计算严格上升子序列
• 根据Dilworth定理，最少系统数等于最长严格上升子序列长度

时间复杂度分析

• 两种计算都使用了O(nlogn)的算法：
• 外层循环遍历所有导弹：O(n)
• 内层使用二分查找：O(logn)
• 总时间复杂度：O(nlogn)

示例验证

输入样例：

389 207 155 300 299 170 158 65

执行过程：

1. 最长不上升子序列计算：

• 维护的d数组变化：

  [389]

  [389,207]

  [389,207,155]

  [389,300,155] (300替换207)

  [389,300,299]

  [389,300,299,170]

  [389,300,299,170,158]

  [389,300,299,170,158,65]

• 最终长度：6

2. 最长严格上升子序列计算：

• 维护的d数组变化：

  [389]

  [207] (替换389)

  [155] (替换207)

  [155,300]

  [155,299] (替换300)

  [155,170] (替换299)

  [155,158] (替换170)

  [65,158] (替换155)

• 最终长度：2

输出：

6
2

代码优化建议

1. 可以合并两个计算过程的公共代码，减少重复
2. 添加输入验证，确保输入数据的有效性
3. 使用更清晰的变量名，如用maxNonIncreasingLen代替len

关键点说明

1. 贪心+二分的正确性：

• 维护的d数组并不一定是真实的子序列，但长度是正确的
• 通过替换操作保证了后续数字的扩展可能性

2. Dilworth定理的应用：

• 将导弹序列视为偏序集
• 最少链划分等于最长反链长度

3. 边界处理：

• 代码正确处理了n=1的情况
• 二分查找的边界条件处理得当

总结

这段代码高效地解决了导弹拦截问题，通过：

1. 贪心算法维护可能的子序列
2. 二分查找优化查找过程
3. 两次遍历分别解决两个子问题
4. 正确应用了组合数学中的Dilworth定理

最终实现了O(nlogn)时间复杂度的解决方案，能够高效处理大规模输入。

好吧。DeepSeek又跟我讲了半天终于弄出了动态规划的解法：

#include <iostream>
using namespace std;
int n = 1, hei[100005], dp1[100005], dp2[100005];
int main()
{
    while (cin >> hei[n++])
    {
        dp1[n - 1] = 1; // 初始化dp1
        dp2[n - 1] = 1; // 初始化dp2
    }
    n -= 2;

    // 计算最长不上升子序列（dp1）
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (hei[j] >= hei[i])
                dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }
    int ans1 = 0;
    for (int i = 1; i <= n; i++)
        ans1 = max(ans1, dp1[i]);

    // 计算最长严格上升子序列（dp2）
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (hei[j] < hei[i])
                dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }
    int ans2 = 0;
    for (int i = 1; i <= n; i++)
        ans2 = max(ans2, dp2[i]);

    cout << ans1 << "\n" << ans2;
    return 0;
}