본문 바로가기

알고리즘 관련/BOJ

BOJ)2157 여행

문제: icpc.me/2157


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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, -1sizeof(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(11)>? func(11) : 0);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2056 작업  (0) 2017.04.06
BOJ)7579 앱  (0) 2017.04.05
BOJ)2618 경찰차  (2) 2017.04.05
BOJ)2688 줄어들지 않아  (0) 2017.04.04
BOJ)2230 수 고르기  (0) 2017.04.04