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; }
感想
なぜかすんなり解けた.
わかりやすい解説を書くのが難しい.読みにくかったらごめんなさい.