Comet OJ - Contest #6 B.双倍快乐（二维最大上升子序列和）-布布扣-bubuko.com

Illyasviel："老板，给我整两个最长不下降子序列，要最大的。"

提示

样例解释：

第一个序列选了 "5"

第二个序列选了 "3 4 4 6"

总和为

https://cometoj.com/contest/48/problem/B

二维LIS变式求两不相交上升子序列最大和。

非常好的一道题。其中思想与一维LIS相似只不过拓展到二维，dp[i][j]表示两序列分别以i，j为结尾的最大和，通过两重for来枚举i，j的情况。

这里有一个巧妙的性质：虽然i，j在枚举时会有相同的情况，但是dp只对含k的情况更新，而k!=i与j即两下标不会相等，所以这里保证了两序列不会有相交的元素。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[505];
int dp[505][505];

int main()
{
    int n,m,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(k=1;k<=n;k++){
        for(i=0;i<k;i++){
            for(j=0;j<k;j++){
                if(a[i]<=a[k]){
                    dp[k][j]=max(dp[k][j],dp[i][j]+a[k]);
                }
                if(a[j]<=a[k]){
                    dp[i][k]=max(dp[i][k],dp[i][j]+a[k]);
                }
            }
        }
    }
    int ans=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            ans=max(ans,dp[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}