动态规划２：最长不下降子序列－－连续序列＋不连续序列-蒲公英云

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

梦里梦外; 2023-07-09 02:01 110阅读 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 */