Comet OJ - Contest #6 problemB - 双倍快乐

题目链接
思路：考虑 $dp\left[i\right]\left[j\right]$dp[i][j]表示两个不下降子序列一个末尾在 $i$i，一个末尾在 $j$j，( $i\&lt;j$i<j)。
然后每次新加一个数 $a\left[k\right]$a[k]，枚举 $i,j$i,j的位置进行转移。
1. $a\left[k\right]\ge a\left[i\right],dp\left[j\right]\left[k\right]=max\left(dp\right[j\left]\right[k],dp[i\left]\right[j]+a[k\left]\right)$a[k]≥a[i],dp[j][k]=max(dp[j][k],dp[i][j]+a[k])
2. $a\left[k\right]\ge a\left[j\right],.dp\left[i\right]\left[k\right]=max\left(dp\right[i\left]\right[k],dp[i\left]\right[j]+a[k\left]\right)$a[k]≥a[j],.dp[i][k]=max(dp[i][k],dp[i][j]+a[k])

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,a[N],dp[555][555],ans;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int k=1;k<=n;k++){
		for(int i=0;i<k;i++){
			for(int j=i;j<k;j++){
				if(a[k]>=a[i])
					dp[j][k]=max(dp[j][k],dp[i][j]+a[k]);
				if(a[k]>=a[j])
					dp[i][k]=max(dp[i][k],dp[i][j]+a[k]);

			}
		}
	}	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)ans=max(ans,dp[i][j]);
	}
	cout<<ans<<endl;
	return 0;
}