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