2012-11-06 22:49:37Morris
[ZJ][DP] a571. 海港碼頭
內容 :
海港碼頭 |
Background
根據 b178. 遊輪 Boat,就是離岸較近的船不可以比離岸較遠的船先離開,不然就會被卡住出不去了。就好比堆疊(stack)結構。
The Problem
給一個碼頭及所有船的到達時間與離開時間,請問最多能讓多少船隻停泊。
注意 : 同一時間只能有一艘船進行進港或離港的操作。
輸入說明
:
多筆測資,每組第一行有一個數字 N 代表有多少個船隻進出港的時間資料,接下來有 N 行資料,每行上有兩個數字 S 與 E 代表一艘船的入港時間與離港時間。
1≦N≦100, 1 ≦ S < E ≦ 1,000,000
輸出說明
:
輸出能分配的最大數量。
範例輸入 :
4 1 10 2 5 3 7 6 9 3 10 12 10 15 13 17 2 1 10 10 12
範例輸出 :
3 2 1
提示
:
※ 題目重覆、測資有問題請通知我。
出處
:
(管理:morris1028)
很明顯地是請你找到最多括弧匹配。
先對數據離散化, 出來最慘 m = 2n, 對於一個位置 dp[i, j]
(i, j 是某一段起始時間與結束時間), 因此我們求 dp[i, j] 的最佳值會來自於 dp[i+1, j] or dp[i, j-1],
或者是可以拆分的的合併 max(dp[i, k]+dp[k+1][j]);
又或者是加上有一艘船在 (i, j) 操作 max(dp[i+1, k]+dp[k+1][j-1]+1);
效率 O(n^3)
很明顯地是請你找到最多括弧匹配。
先對數據離散化, 出來最慘 m = 2n, 對於一個位置 dp[i, j]
(i, j 是某一段起始時間與結束時間), 因此我們求 dp[i, j] 的最佳值會來自於 dp[i+1, j] or dp[i, j-1],
或者是可以拆分的的合併 max(dp[i, k]+dp[k+1][j]);
又或者是加上有一艘船在 (i, j) 操作 max(dp[i+1, k]+dp[k+1][j-1]+1);
效率 O(n^3)
#include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, tn;
while(scanf("%d", &n) == 1) {
int S[105], T[105], i, j, k;
map<int, int> r;
for(i = 0; i < n; i++) {
scanf("%d %d", &S[i], &T[i]);
r[S[i]] = 1, r[T[i]] = 1;
}
i = 0;
for(map<int, int>::iterator it = r.begin();
it != r.end(); it++) {
it->second = i;
i++;
}
tn = i+1;
int dp[210][210] = {};
char has[210][210] = {};
for(i = 0; i < n; i++) {
dp[r[S[i]]][r[T[i]]] = 1;
has[r[S[i]]][r[T[i]]] = 1;
}
int ans = 1;
for(i = 0; i < tn; i++) {
for(j = 0; j+i < tn; j++) {
if(i)
dp[j][j+i] = max(max(dp[j+1][j+i], dp[j][j+i-1]), dp[j][j+i]);
for(k = j; k < j+i; k++) {
dp[j][j+i] = max(dp[j][j+i], dp[j][k]+dp[k+1][j+i]);
dp[j][j+i] = max(dp[j][j+i], dp[j+1][k]+dp[k+1][j+i-1]+has[j][j+i]);
}
if(dp[j][j+i] > ans)
ans = dp[j][j+i];
}
}
printf("%d\n", ans);
}
return 0;
}