mayoko’s diary

プロコンとかいろいろ。

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;
}