2572번: 보드게임

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

채점 데이터 내에서 시작 마을과 연결된 마을이 없어 움직일 수 없는 경우도 있는데 이럴땐 0을 출력해야 한다.

$O(nk)$

dp[i][j]: i번 카드를 내서 j번 마을에 도착할 때 얻을 수 있는 최대 점수

#include<cstdio>
#include<algorithm>
using namespace std;
struct st {
    int x, y;
    char c;
}e[10000];
int n, m, k, dp1[501], dp2[501];
char c[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf(" %c", c + i);
    scanf("%d%d", &m, &k);
    for (int i = 0; i < k; i++) scanf("%d%d %c", &e[i].x, &e[i].y, &e[i].c);
    fill(dp1 + 2, dp1 + 1 + m, -1e6);
    for (int i = 0; i < n; i++) {
        fill(dp2 + 1, dp2 + 1 + m, -1e6);
        for (int j = 0; j < k; j++) {
            dp2[e[j].y] = max(dp2[e[j].y], dp1[e[j].x] + (c[i] == e[j].c));
            dp2[e[j].x] = max(dp2[e[j].x], dp1[e[j].y] + (c[i] == e[j].c));
        }
        copy(dp2, dp2 + 1 + m, dp1);
    }
    printf("%d", *max_element(dp1, dp1 + 1 + m) * 10);
    return 0;
}