글 읽기 - 반례 찾고싶습니다.

hsw0194 3년 전 0

점화식 논리는 맞는거같은데 어느부분에서 틀린지 헷갈립니다.. 도와주세요ㅠㅠ

#include <iostream>
#include <vector>

using namespace std;

#define N_MAX 10001
#define M_MAX 501

int N, M;
// vector<vector<int>> dp(N_MAX, vector<int>(M_MAX, 0));
int dp[N_MAX][M_MAX];

int D[1001];

int ans();

int main(void) {
  cin >> N >> M;

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

  cout << ans();
}

int ans() {
  dp[1][0] = 0;
  dp[1][1] = D[1];

  for (int i = 2; i <= N; i++) {
    for (int j = 0; j <= M; j++) {
      if (j > 0) {
        // i분일때 체력이 j인것은
        // i-1분일때 체력이 j-1에서 i분일때 D[i]만큼 뛰거나
        // i-1분일때 체력이 j+1에서 i분일때 쉬거나
        dp[i][j] = max(dp[i - 1][j - 1] + D[i], dp[i - 1][j + 1]);
      } else {
        // i분일때 체력이 0일때의 거리는
        // i-1분일때 체력이 1일때 최대거리와 (뛰지 않으니)
        // i-1분일때 체력이 0일때 최대거리 중 최대(연속해서 쉬는것)
        dp[i][0] =max(dp[i-1][1],dp[i-1][0]);
      }
    }
  }

  return dp[N][0];
}

djs100201 3년 전 0

또한 학생들이 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수가 없다.

8 3
100 100 1 1000 2000 1 1 1

output:3200

answer:3101

hsw0194 3년 전 0

dp를 3차원으로 구성해야할까요?

djs100201 3년 전 1

저는 3차원으로 했습니다

hsw0194 3년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

반례 찾고싶습니다.

hsw0194 3년 전 0

djs100201 3년 전 0

hsw0194 3년 전 0

djs100201 3년 전 1

hsw0194 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말