题目描述
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
9
5 3 2 1 4 2 1 4 6
样例输出 1
22
提示
样例解释：
第一个序列选了 "5"
第二个序列选了 "3 4 4 6"
总和为 22。
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[];
int dp[][]; int main()
{
int n,m,i,j,k;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(k=;k<=n;k++){
for(i=;i<k;i++){
for(j=;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=;
for(i=;i<=n;i++){
for(j=;j<=n;j++){
ans=max(ans,dp[i][j]);
}
}
printf("%d\n",ans);
return ;
}
