Comet OJ 双倍快乐

双倍快乐

f[i][j]: 两个子序列分别以i和j结尾时的最大和.
LIS的变形,每次可将第k个元素尝试添加到两个序列里.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int a[505];
int f[505][505];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  int ans=0;
  for(int k=1;k<=n;++k){
    for(int i=0;i<k;++i){
      for(int j=0;j<k;++j){
          if(a[k]>=a[i]) {
            f[k][j]=max(f[k][j],f[i][j]+a[k]);
          }
          if(a[k]>=a[j]){
            f[i][k]=max(f[i][k],f[i][j]+a[k]);
          }
      }
    }
  }
  for(int i=0;i<=n;++i){
    for(int j=0;j<=n;++j){
      ans=max(ans,f[i][j]);
    }
  }
  cout<<ans<<endl;
  return 0;
}