最长不下降自序列（最长递增子序列）C++动态规划

你的名字 2022-08-29 15:52 161阅读 0赞

题目：[http://www.kencoding.net/problem.php?id=1112][http_www.kencoding.net_problem.php_id_1112]

最长递增子序列（Longest Increasing Subsequence , LIS）问题：给定一个长度为N的数组，找出一个最长的单调递增子序列。例如一个长度为7的序列 A = 5 , 6 , 7 , 4 , 2 , 8 , 3 A=\{5,6,7,4,2,8,3\} A=5,6,7,4,2,8,3，它最长的单调递增子序列为 5 , 6 , 7 , 8 \{5,6,7,8\} 5,6,7,8，长度为4.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]

此题答案，也是最长不下降自序列的固定模板：

#include <cstdio>
     
    int a[1000];
    int n;
    int f[1000];
     
    int main(){ 
        scanf("%d",&n);
        int i;
        int j;
        for (i=1;i<=n;i++){ 
            scanf("%d",&a[i]);
        }
     
        //每个点的f值不可能小于1
        for(i=1;i<=n;i++) f[i] =1;
     
        int max = 1;
        for (i=2;i<=n;i++){ 
            for(j=1;j<i;j++){ 
                if( a[j] <= a[i] && f[i] < f[j]+1){ 
                    f[i] = f[j]+1;
                    if(max < f[i])
                        max = f[i];
                }
            }
        }
     
        printf("%d",max);
     
        return 0;
    }

下面给出一个例题

**导弹拦截系统** [hdu 1257][]

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.  
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int MAXN = 100010;
    
    int n, high[MAXN];
    int LIS(){ 
        int ans = 1;
        int dp[MAXN];
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        { 
            int max= 0;
            for (int j = 1; j < i; j++)
            { 
                if (dp[j] > max && high[j] < high[i])
                    max = dp[j];
            }
            dp[i] = max + 1;
            if (dp[i] > ans)
                ans = dp[i];
        }
        return ans;
    }
    int main(){ 
        while (cin >> n)
        { 
            for (int i = 1; i <= n; i++)
            { 
                cin >> high[i];
            }
            cout << LIS() << endl;
        }
    }

[http_www.kencoding.net_problem.php_id_1112]: http://www.kencoding.net/problem.php?id=1112
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/e58124633f374cd49c10df581d000e8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/ef82616b7c06481a86b591fb64727168.png
[hdu 1257]: http://acm.hdu.edu.cn/showproblem.php?pid=1257
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220829/ece9613cdd7c454c9b2f4bd729874dca.png