Indeedなう C Optimal Recommendations - いろんなことで四苦Hack（仮）

めっちゃトイレ行きたい。えぬわいです。

続きです。

いい感じのDP問題だと思いました。

3 変数だと考えにくいので、2 変数で、DPテーブルを考察してみたら。サクッと行けました。

サクッと行けた。嘘です。入力のところで、dpテーブルの同じインデックスのところには、大きい方を代入しないといけない点を忘れてました。

dp[i+1][j+1][k+1] := i, j, k の最大収入

です。

TLEったので、C++で書きました。

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[102][102][102];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int a, b, c, w;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &a, &b, &c, &w);
        dp[a][b][c] = max(w, dp[a][b][c]);
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            for (int k = 0; k <= 100; k++) {
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k]);
                dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k]);
                dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]);
            }
        }
    }
    int x, y, z;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        printf("%d\n", dp[x][y][z]);
    }
    return 0;
}