2572 보드게임

백준 2572 보드게임 https://www.acmicpc.net/problem/2572

완전탐색으로 풀려고 했는데 겹치는 부분문제가 보여서 DP로 풀었다.
(완전탐색 TLE날듯)

$DP[N][M]$ : 현재 N번 카드이면서 M번 마을에 있을 때 최대점수

$DP[N][M]$ = $max(DP[N][M], DP[N+1][adj[M][K]] + plus)$

#include <cstdio> #include <vector> #include <cstring> using namespace std; inline int max(int a, int b){ return a > b ? a : b; } int C,N,M; char card[1001]; int dp[1001][501];        //card, vertex vector<pair<char, int>> adj[1001]; int solve(int ca, int ver){     if (ca == C) return 0;       int &ret = dp[ca][ver];     if (ret != -1) return ret;     ret = 0;       for (auto n : adj[ver]){         int next = n.second;         ret = max(ret, solve(ca + 1, next) + (card[ca] == n.first ? 10 : 0));     }     return ret; } int main(){     memset(dp, -1, sizeof(dp));       scanf("%d", &C);     for (int n = 0; n < C; n++)         scanf(" %c", &card[n]);     scanf("%d%d", &N, &M);     for (int m = 0; m < M; m++){         int u, v;         char d;         scanf("%d%d %c", &u, &v, &d);         adj[u].push_back(make_pair(d, v));         adj[v].push_back(make_pair(d, u));     }     printf("%d\n",solve(0, 1));     return 0; } Colored by Color Scripter

cs