じゃんけん [技術室奥プログラミングコンテスト#4 Day1 L]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6671950

制約を見ると、N,M,Kと小さめの値になっている。
自分はこれと最大値という所からDPかなと思い、DPで考えると解けた。
間がちょっと抜けているが、説明ができない。

dp[k][cu] := k回終えてanmichiくんが頂点cuにいる時のスコアの最大値
辺の数も5000に抑えられているので、これを更新していけば解ける。
発展的な話になるが、今回はdp[2001][2000]と宣言しなくても、dp[2][2000]で解くことができる。
メモリの節約をしているわけだが、こちらも練習しておくとよい。

int N, M, K, X, Y;
vector<int> E[2020];
char C[2020];
int D[2010];
int dp[2010][2010];
//---------------------------------------------------------------------------------------------------
inline int get(char me, char you) {
    if (me == you) return Y;
    if (me == 'G' and you == 'C') return X;
    if (me == 'C' and you == 'P') return X;
    if (me == 'P' and you == 'G') return X;
    return 0;
}
void _main() {
    cin >> N >> M >> K >> X >> Y;
    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    rep(i, 0, N) cin >> C[i];
    rep(i, 0, K) {
        cin >> D[i];
        D[i]--;
    }

    rep(k, 0, K + 1) rep(cu, 0, N) dp[k][cu] = -inf;
    dp[0][0] = 0;
    rep(k, 0, K) rep(cu, 0, N) if (0 <= dp[k][cu]) {
        chmax(dp[k + 1][cu], dp[k][cu] + get(C[cu], C[D[k]]));
        fore(to, E[cu]) chmax(dp[k + 1][to], dp[k][cu] + get(C[to], C[D[k]]));
    }

    int ans = 0;
    rep(cu, 0, N) chmax(ans, dp[K][cu]);
    cout << ans << endl;
}