글 읽기 - 가장 긴 바이토닉 부분수열 접근 방법에 대해..

jopemachine 2년 전 0

저는 이 문제를 점화식을 조금 바꿔서 풀어보려고 시도해보았습니다..

k가 되는 점 (수열의 오름차순, 내림차순 순서가 바뀔 때)에서 curved를 1로 만들어 한 번만 꺽이도록 풀어보려 했는데 예제 입력 1의 답도 구하지 못했습니다.. (정답은 7이나 5 출력)

이 방법으로 문제를 풀 수 없는 이유가 궁금합니다ㅠ

#include <vector>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <algorithm>
#include <array>
#include <memory.h>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

int N;

int nums[1001];
int dp[1001][2];

int go (int idx, int curved) {
  int& ans = dp[idx][curved];
  if (ans != -1) return ans;
  if (idx >= N) return 1;

  ans = 1;

  for (int i = idx + 1; i < N; ++i) {
    bool cond = curved == 1 ?
      (nums[idx] > nums[i]) : (nums[idx] < nums[i]);

    if (cond) {
      ans = max(ans, go(i + 1, curved) + 1);
    }

    else {
      if (curved == 0) {
        ans = max(ans, go(i + 1, 1) + 1);
      }
    }
  }

  return ans;
}

int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  cin >> N;

  for (int i = 0; i < N; ++i) {
    cin >> nums[i];
  }

  int maxVal = 0;

  for (int i = 0; i < N; ++i) {
    memset(dp, -1, sizeof(dp));
    maxVal = max(maxVal, go(i, 0));
  }

  cout << maxVal << "\n";

  return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

가장 긴 바이토닉 부분수열 접근 방법에 대해..

jopemachine 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말