Typical DP Contest L - 猫
解法
dp[i][j] = (猫 i までの幸福度の最大値。ただし, 猫 i は 猫 j, j+1, ..., i の猫と距離 1 以内の場所にいる) という dp を考えます。すると, dp の遷移は
dp[i+1][j] = max(0 <= k <= j)(dp[i][k]) + sum(j <= k <= i+1)(f[i+1][k]) となります。
sum の部分については事前に累積和を計算しておけば O(1) です。また, 前半の dp の最大値を求めるパートについても, j を 1 増やすごとに max 値を更新していけば O(1) で更新していけるので簡単です。
const int MAXN = 1111; int f[MAXN][MAXN]; int dp[MAXN][MAXN]; int sum[MAXN][MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> f[i][j]; for (int i = 0; i < N; i++) { for (int j = 1; j <= i; j++) { sum[i][j] = sum[i][j-1] + f[i][j-1]; } } for (int i = 1; i < N; i++) { int maxi = -1e9; for (int j = 0; j <= i; j++) { maxi = max(maxi, dp[i-1][j]); dp[i][j] = maxi + (sum[i][i]-sum[i][j]); } } int ans = -1e9; for (int i = 0; i < N; i++) ans = max(ans, dp[N-1][i]); cout << 2*ans << endl; return 0; }