Typical DP Contest L - 猫

解法

1 <= N <= 1000 なので,普通のDPするとすれば 2 つキーとして使える.
1つは今見ているのが何番目かに使うとして,もう1つを何にするかが問題.

自分は,どの猫まで距離1以内に配置するか,と考えた.つまり
dp[i][j] := i 番目の猫まで考えた時,i 番目の猫は"自分より前の猫で" j 番目の猫まで距離 1 以内にいるときの最大値 (j <= i)
とした.

すると,遷移は以下のように書ける.
sum[j] := f[i][i] + f[i][i - 1] + ... + f[i][j]
dp[i][j] := max(dp[i - 1][k]) + sum[j] (k = 1, 2, ..., j)

もし i 番目の猫が j 番目の猫まで距離1以内に配置するとき,i - 1番目の猫は,すくなくとも j 番目の猫までは距離 1 以内にいる必要がある.ただし,それ以前の猫をどこまで距離 1 以内に配置するかについては自由であることがわかる.
(i - 1 番目の猫が k (<= j) 番目までの猫と距離 1 以内で,i番目の猫が j 番目のまでの猫と距離 1 以内であるような配置は必ず存在する.言葉だとわかりにくいけど実験で色々配置してみるとわかるはず.)

なのでさっきの遷移でよい.
しかしこのままだと max とる部分で追加 O(N) かかるので,どうにかしないといけない.
よく見ると,max(dp[i - 1][k]) については j についてのループの外側に出せる.
ma[k] := max(dp[i - 1][m]) (m = 1, ..., k)
としてやれば,さっきの遷移は
dp[i][j] := ma[j] + sum[j]
となって,O(N^2)で解ける.

max(dp[N][i]) が答えだが,実は f[i][j] しかカウントしてないので,f[j][i] の分も含めて2倍する必要がある.(f[i][j] == f[j][i])

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1e9;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> f(N, vector<int>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            cin >> f[i][j];
        }
    }

    vector<vector<int>> dp(N + 1, vector<int>(N + 1, -INF));
    dp[0][0] = 0;
    vector<int> ma(N + 1);
    for(int i = 1; i <= N; ++i) {
        int sum = 0;
        for(int j = i; j >= 0; --j) {
            if(j != 0) {
                sum += f[i - 1][j - 1];
            }
            dp[i][j] = max(dp[i][j], ma[j] + sum);
        }
        for(int j = 0; j <= N; ++j) {
            ma[j] = dp[i][j];
            if(j != 0) {
                ma[j] = max(ma[j], ma[j - 1]);
            }
        }
    }
    cout << *max_element(dp[N].begin(), dp[N].end()) * 2 << endl;
}

感想

なぜかすんなり解けた.
わかりやすい解説を書くのが難しい.読みにくかったらごめんなさい.