CometOJ#6 雙倍快樂（簡單DP）

鏈接：https://www.cometoj.com/contest/48/problem/B

題意：給出一串數列，要求在這個數列中找出兩條“不相交”的非下降子序列使得子序列之和最大。“不相交”即不存在任意的ai同時存在于兩個子序列中。

分析：筆者刷題量不多，這道題對筆者加深動態規劃求子序列的理解很有幫助；題目要求非下降子序列的最大和，這里我們要求的是兩條子序列。做題時的第一想法是走兩遍DP，先求出一條和最大的子序列，把這條子序列中的元素給剔除，接著再重復該步驟，得到另一條和最大的子序列，最后把兩條子序列的和加起來。但是，這種做法是存在后效性的，我們的目的是要求得兩條子序列的和最大，如果每次只是單純的找和最大的子序列，那么很有可能在第一次選元素時就斷了使得子序列總和最大的“橋梁”。好比方說：5 4 4 5 4；通過該方案得到的兩條序列會是：“4 4 5”、“5”，最終結果是18。但最優的方案其實是：“4 4 4”、“5 5”，結果為22。

　　設dp[i][j]為兩條子序列的末端分別為i和j時的子序列和，dp[0][0] = 0;其狀態轉移方程可以由單個子序列的轉移方程推廣得到，詳見代碼部分。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    scanf("%d",&n);

    int num[n+1];
    num[0] = 0;
    for (int i=1;i<=n;i++) {
        scanf("%d",&num[i]);
    }

    int dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    int ans = 0;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<i;j++) {
            if (num[i] >= num[j]) {
                for (int k=0;k<i;k++) {
                    dp[i][k] = max(dp[i][k],dp[j][k] + num[i]);
                    dp[k][i] = max(dp[k][i],dp[k][j] + num[i]);
                    ans = max(ans,max(dp[i][k],dp[k][i]));
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

?