Typical DP Contest L - 猫

問題

一次元上に猫1, ..., Nをこの順に並べる。
猫同士には仲のよさf[i][j]が定まっている。

i番の猫の幸福度は、i番目の猫から距離1にいる猫の仲のよさの総和である。
猫を最適に並べたときの、幸福度の総和の最大値を求めよ。

制約条件

N≦1000
f[i][j]の絶対値≦1000

方針

dp[i][j] := 猫iまで並べたとき、i番目の猫から距離1以内にいる猫のうち最も小さい番号がjであるようなときの幸福度の総和の最大値

として、これを更新するDP.
dp[i][j] = max{dp[i - 1][k] + sum[j][i] | k ≦ j }という漸化式になる。
kを全部見るとO(n^3)でTLEになるが、
sumを前計算しておき、max{dp[i - 1][k]}はjが増えるたびにmaxをとって更新していけば
O(n^2)で計算できる。

ソースコード

昔の自分はトチ狂ってsegment木を使ったようだ。

int n, f[1000][1000];
int N, dat[2][2048], sum[1000][1000];
 
inline void init(int *dat){
	rep(i, 2*N) dat[i] = -inf;
}
inline void update(int *dat, int i, int v){
	i += N - 1;
	dat[i] = max(dat[i], v);
	while(1){
		i = (i - 1) / 2;
		dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
		if(i == 0) break;
	}
}
inline int query(int *dat, int a, int b, int k, int l, int r){
	if(a <= l && r <= b) return dat[k];
	if(b <= l || a >= r) return -inf;
	
	int lch = query(dat, a, b, k * 2 + 1, l, (l + r) / 2);
	int rch = query(dat, a, b, k * 2 + 2, (l + r) / 2, r);
	return max(lch, rch);
}
 
int main(){
	cin >> n;
	rep(i, n) rep(j, n) cin >> f[i][j];
	rep(i, n) for(int j = i; j < n; j++) sum[i][j] = (j ? sum[i][j - 1] : 0) + f[i][j];
	
	for(N = 1; N < n; N *= 2);
	int cur = 0, next = 1;
	
	init(dat[0]);
	rep(i, n) update(dat[0], i, sum[0][i]);
	
	for(int i = 1; i < n; i++){
		init(dat[next]);
		
		for(int j = i; j < n; j++){
			int q = query(dat[cur], i - 1, j + 1, 0, 0, N);
			update(dat[next], j, q + sum[i][j]);
		}
		swap(cur, next);
	}
	cout << 2 * query(dat[cur], n-1, n, 0, 0, N) << endl;
	
	return 0;
}

普通に書くとこんなかんじ

int n, f[1000][1000];
ll dp[1001][1001];

int main(){
	scanf("%d", &n);
	rep(i, n) rep(j, n) scanf("%d", f[i] + j);
	
	rep(i, n + 1) rep(j, n + 1) dp[i][j] = -inf;
	dp[0][0] = 0;
	
	rep(i, n){
		vector<ll> sum(1, 0LL);
		rep(j, i) sum.pb(sum.back() + f[i][i - j - 1]);
		reverse(all(sum));
		
		ll mx = -inf;
		
		rep(j, i + 1){
			
			mx = max(mx, dp[i][j]);
			dp[i + 1][j] = mx + sum[j];
			
		}
	}
	cout << *max_element(dp[n], dp[n] + n) * 2 << endl;
	
	return 0;
}