2157번: 여행

https://www.acmicpc.net/problem/2157


$O(m(n+k))$

a<b인 (a,b,c) 쌍에 대해 b->a, 가중치 c 간선을 만들면 DAG를 만들 수 있다.
DAG 상에서 최장 거리는 dp를 통해 구할 수 있다.
dp[n][m]: 1-> ... -> n으로 m번 이하에 도착하는 최대 점수

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, k, dp[301][301];
vector<pair<int, int> > adj[301];
int f(int x, int y) {
    if (x > 1 && y == 1) return -1e9;
    if (x>1 && !dp[x][y]) {
        dp[x][y] = -1e9;
        for (auto it : adj[x]) dp[x][y] = max(dp[x][y], f(it.first, y - 1) + it.second);
    }
    return dp[x][y];
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0, x, y, z; i < k; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if (x<y) adj[y].push_back({ x,z });
    }
    printf("%d", f(n, m));
    return 0;
}