Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2010-day4 lake

問題文 :

解法 :

まず,

dp[l][r] = 区間[l, r]での運行数の最大値, とすると
dp[l][r] = max(dp[l][r], dp[l][s[i] - 1] + dp[s[i] + 1][t[i] - 1] + dp[t[i] + 1][r]);

となる. ただし, s[i], t[i]はそれぞれ船の来航する地点の座標で, s[i] < t[i]とする.

これは, t[i]について昇順に並べると正しくdpができ, O(N^3)時間で問題を解くことが出来る. 50 点が期待できる.

ここで, dp[l][r]を, 別の方法で更新していくことを考えてみよう.
幅 1 刻みで dpテーブルを更新する (dp[x][x + 1], dp[x][x + 2], ... dp[x][x + i]) ことで, 上と同じ漸化式がO(N^2)時間で計算可能となる.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int s[2048], t[2048], pos[4096];
int dp[4096][4096];

int main()
{
	int xs[4096];
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		scanf("%d %d", s + i, t + i);
		xs[i * 2] = s[i]; xs[i * 2 + 1] = t[i];
	}
	sort(xs, xs + 2 * n);
	
	for (int i = 0; i < n; i++){
		s[i] = lower_bound(xs, xs + 2 * n, s[i]) - xs + 1;
		t[i] = lower_bound(xs, xs + 2 * n, t[i]) - xs + 1;
		pos[s[i]] = t[i]; pos[t[i]] = s[i];
	}
	
	for (int d = 1; d < 2 * n; d++){
		for (int x = 1; x + d <= 2 * n; x++){
			dp[x][x + d] = max(dp[x + 1][x + d], dp[x][x + d - 1]);
			
			if (x <= pos[x] && pos[x] <= x + d) dp[x][x + d] = max(dp[x][x + d], dp[x][pos[x] - 1] + dp[pos[x] + 1][x + d] + 1);
			if (x <= pos[x + d] && pos[x + d] <= x + d) dp[x][x + d] = max(dp[x][x + d], dp[x][pos[x + d] - 1] + dp[pos[x + d] + 1][x + d] + 1);
		}
	}
	
	printf("%d\n", dp[1][2 * n]);
	
	return (0);
}