双倍快乐

题目描述

 

Illyasviel："你想要最长不下降子序列吗？"

star-dust："好啊！"

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

求序列 a 中的两个不相交的不下降子序列使得他们的元素和的和最大，子序列可以为空。

注 1：序列 a 不下降的定义是不存在 l<r 且 al​>ar​

注 2：两个子序列不相交的定义是：不存在 ai​ 即在第一个子序列中也在第二个子序列中。

 

输入描述

 

第一行一个数字 n 代表序列 a 的长度。

接下来一行 n 个数，第 i 个数代表 ai​。

数据范围：

• 2≤n≤500
• 1≤ai​≤105

 

输出描述

 

一行一个整数代表两个不相交的不下降子序列的元素和的最大值。

 

样例输入 1 

95 3 2 1 4 2 1 4 6

样例输出 1

22

提示

样例解释：

第一个序列选了 "5"

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

总和为 22。

 

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

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

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

 

#include
          
           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