Typical DP Contest L - 猫

問題文 : 猫

解法 :

区間 DP である.

まず, 各猫について $a_1 \leqq a_2 \leqq \cdots \leqq a_n$ かつ$a_i \leqq i$ を満たすならば, 区間 $[a_i,\ i]$ の猫の幸せ度の和を最大化する問題に昇華することができる. そこで, 区間$[a_i,\ i]$ の$i$ 番目の猫の幸せ度の和を $sum[l][r]$ とし, 次のような dp を考える.
$dp[l][r] :=$ 区間$[l,\ r]$ の猫が仲良しグループの時の猫$r,\ \cdots, n$ の幸せ度の総和とすると

$dp[l][r] = \text{sum}[l][r] + \max_{i = l \cdots r + 1}(dp[i][r + 1])$
$dp[x][n] = \text{sum}[x][n]$

となる. 遷移 $O(n)$, 空間$O(n^2)$ なので全体で$O(n^3)$ の dp となる. $n \leqq 10^3$ で, AtCoder 補正とかでぎりぎり間に合う.

#include <bits/stdc++.h>

using namespace std;

int n;
int rel[1024][1024], sum[1024][1024], memo[1024][1024];

int findMax(int l, int r)
{
	if (r == n - 1) return (sum[l][r]);
	if (memo[l][r] != INT_MIN) return (memo[l][r]);
	
	int ret = 0;
	
	for (int i = l; i <= r + 1; i++) ret = max(ret, findMax(i, r + 1));
	
	return (memo[l][r] = ret + sum[l][r]);
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &rel[i][j]);
	
	
	for (int d = 1; d < n; d++){
		for (int x = 0; x + d < n; x++){
			sum[x][x + d] = sum[x + 1][x + d] + rel[x][x + d];
		}
	}
	
	for (int i = 0; i < 1024; i++) for (int j = 0; j < 1024; j++) memo[i][j] = INT_MIN;
	printf("%d\n", 2 * findMax(0, 0));
	
	return (0);
}