PKU 1036

少し読解困難だった．
はTLEするが，の処理は外に出すことができるためとなる．

dp[i][j] := i時間で扉がjの状態であるときに，来訪するgang達の価値の総和の最大値

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

const int INF = 1 << 30;

int dp[2][101];

int main() {
    int N, K, T, t[101], p[101], s[101], ans = 0;

    cin >> N >> K >> T;

    for(int i = 0; i < N; i++) { scanf("%d", &t[i]); }
    for(int i = 0; i < N; i++) { scanf("%d", &p[i]); }
    for(int i = 0; i < N; i++) { scanf("%d", &s[i]); }

    for(int i = 0; i < 2; i++) for(int j = 0; j <= K; j++)
        dp[i][j] = -INF;

    dp[0][0] = 0;

    for(int i = 1; i <= T; i++) {
        int n = i & 1;
        int c = !n;

        for(int j = 0; j <= K; j++) {
            dp[n][j] = dp[c][j];
            if(j+1 <= K) dp[n][j] = max(dp[n][j], dp[c][j+1]);
            if(j-1 >= 0) dp[n][j] = max(dp[n][j], dp[c][j-1]);
        }

        for(int j = 0; j < N; j++) {
            if(i != t[j]) continue;
            dp[n][s[j]] += p[j];
        }
    }

    for(int i = 0; i <= K; i++) {
        ans = max(ans, dp[T&1][i]);
    }

    cout << ans << endl;
}