BOJ)2157 여행

문제: icpc.me/2157

번호가 증가하는 순서대로만 여행을 할 때 1번 도시에서 N번 도시까지 항공편을 K번 이하로만 이용하여 갈 때 얻을 수 있는 기내식 점수의 최댓값을 구하는 문제다.

 dp[pos][val]= pos번 나라까지 여행하고 항공편을 val번 이용했을 때 얻을 수 있는 최대 기내식 점수 로 정의 한 뒤 문제를 해결하면 된다.

소스코드는 탑 다운 방식으로 구현하여 테이블의 정의가 반대다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int a[301][301], n, m, k, dp[301][301], x, y, z;
int func(int pos, int cnt) {
    if (pos == n)return 0;
    if (cnt == m)return -INF;
    int &ret = dp[pos][cnt];
    if (ret != -1)return ret;
    ret = -INF;
    for (int i = pos + 1; i <= n; i++)
        if (a[pos][i])
            ret = max(ret, a[pos][i] + func(i, cnt + 1));
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = max(a[x][y], z);
    }
    printf("%d\n", func(1, 1)>0 ? func(1, 1) : 0);
    return 0;
}