글 읽기 - 틀린 케이스를 못 찾겠습니다.

cheolwan_park 4년 전 0

나름대로 많은 데이터를 넣어봤는데 반례를 못 찾겠습니다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// R[a][b] a -> b 항로의 기내식 점수
//dp[N][M] : N 번 도시까지 M 개의 도시를 거쳤을 때의 기내식 점수 합 최대값
int R[301][301], dp[301][301];  
int N, M, K;
int a, b, c;
constexpr int IMPOS = -0x7fffffff;

int main() {
    scanf("%d%d%d", &N, &M, &K);

    for(int i=0; i<=300; ++i) {
        for(int j=0; j<=300; ++j) 
            dp[i][j] = R[i][j] = IMPOS;
    }

    for(int i=0; i<K; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        R[a][b] = max(R[a][b], c);
    }

    // m = 1
    for(int i=2; i<=N; ++i) {
        if(R[1][i] != IMPOS)
            dp[i][2] = R[1][i];
    }

    // m > 1
    for(int m=3; m<=M; ++m) {
        for(int a=3; a<=N; ++a) {
            for(int b=3; b<a; ++b) {
                if(dp[b][m-1] != IMPOS && R[b][a] != IMPOS)
                    dp[a][m] = dp[b][m-1] + R[b][a];
            }
        }
    }

    int ans=0;
    for(int m=2; m<=M; ++m) {
        ans = max(ans, dp[N][m]);
    }
    printf("%d\n", ans);
}

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

문제

문제

출처

ICPC

틀린 케이스를 못 찾겠습니다.

cheolwan_park 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말