动态规划２：最长不下降子序列－－连续序列＋不连续序列

梦里梦外; 2023-07-09 02:01 11阅读 0赞

//最长不下降子序列－－连续+不连续
    
    #include <cstdio>
    #include "vector"
    #include "algorithm"
    
    using namespace std;
    const int maxn = 10010;
    int A[maxn], dp[maxn];//A存放数字序列　　dp存放以A[i]结尾的连续序列长度
    vector<int> ans[maxn];//ans存放最长子序列
    int dp2[maxn];
    
    void LIS1(int n) { 
        //不连续最长子序列
        int maxdp = 0, maxdpLoc = 0;//记录最长子序列　子序列下标
        for (int i = 0; i < n; i++) { 
            dp[i] = 1;
            ans[i].push_back(1);
            for (int j = 0; j < i; j++) { 
                if (A[j] <= A[i] && dp[j] + 1 > dp[i]) { 
                    dp[i] = dp[j] + 1;
                    ans[j].push_back(A[i]);
                    if (maxdp < ans[j].size()) { 
                        maxdpLoc = j;
                        maxdp = ans[j].size();
                    }
                }
    
            }
    
        }
        printf("len: %d\n", maxdp);
        for (int i = 0; i < maxdp; i++)
            printf("%d ", ans[maxdpLoc][i]);
        printf("\n");
    
    }
    
    void LIS2(int n) { 
        //不连续最长子序列
        int maxdp = 0, maxdpLoc = 0;//记录最长子序列　子序列下标
        dp2[0] = 1;
        for (int i = 1; i < n; i++) { 
    
            if (A[i] >= A[i - 1]) { 
                dp2[i] = dp2[i - 1] + 1;
    
                if (maxdp < dp2[i]) { 
                    maxdp = dp2[i];
                    maxdpLoc = i;
                }
            }
    
        }
        printf("len: %d\n", maxdp);
        for (int i = 0; i < maxdp; i++)
            printf("%d ", A[maxdpLoc - maxdp + i + 1]);
        printf("\n");
    
    }
    
    int main() { 
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) { 
            scanf("%d", &A[i]);
        }
        LIS1(n);
        LIS2(n);
    }
    
    /* 8 1 2 3 -9 3 9 0 11 */

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227004535937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70