提出 #272316

---

ソースコード 拡げる

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int N;
int R[3100];

int solve() {
  int res = 0;
  int dp[3100][2];
  int nxt[3100][2];
  dp[R[0]][0] = 1;
  dp[R[0]][1] = 1;
  for(int i = 0; i < N-1; ++i) {
    for(int j = 0; j < N; ++j) {
      nxt[j][0] = dp[j][0];
      nxt[j][1] = dp[j][1];
    }
    for(int j = 0; j < N; ++j) {
      if(R[i+1] < j && dp[j][0] != 0) {
        nxt[R[i+1]][1] = max(nxt[R[i+1]][1], dp[j][0] + 1);
      }
      if(R[i+1] > j && dp[j][1] != 0) {
        nxt[R[i+1]][0] = max(nxt[R[i+1]][0], dp[j][1] + 1);
      }
    }
    for(int j = 0; j < N; ++j)
      memcpy(dp[j], nxt[j], sizeof(int) * 2);
  }

  for(int j = 0; j < N; ++j) {
    res = max(res, max(dp[j][1], dp[j][0]));
  }
  if(res < 3)
    res = 0;
  return res;
}

int main() {
  cin >> N;
  for(int i = 0; i < N; ++i)
    cin >> R[i];
  for(int i = 0; i < N; ++i) {
    int v = 1000000;
    for(int j = 0; j < N; ++j)
      if(i <= R[j] && R[j] < v)
        v = R[j];
    for(int j = 0; j < N; ++j)
      if(R[j] == v)
        R[j] = i;
  }
  cout << solve() << endl;
  return 0;
}

提出情報

ジャッジ結果