2012-09-25 08:26:47Morris
[CSAPC][dp解] b178. 遊輪 Boat
內容 ： | 正體中文 (zh_TW) | 簡體中文 (zh_CN)
埃及的尼罗河上有很多游轮，虽然可能分别属于不同的公司，但之间有个不成文的默契。当多艘游轮要靠岸时，一种可能是直接停靠在岸边的码头，另一种方式是靠
在已经就位的船旁边。它们可以一艘接着一艘并排起来，离岸较远的船上的游客若要下船，则可以通过其它的船到达岸上。不过有个限制，就是离岸较近的船不可以
比离岸较远的船先离开，不然就会被卡住出不去了。
给所有船只的到达和离开时间，问岸边最少需要几个码头，才能让所有的船有办法靠岸。
给所有船只的到达和离开时间，问岸边最少需要几个码头，才能让所有的船有办法靠岸。
輸入說明
：
输入的第一行有一个整数n，代表游轮的个数。
接下来有n行每一行分别有两个整数Ai,Bi(Ai<=Bi)，代表第i艘游轮的到达和离开时间。
所有船只的到达和离开时间都不会相等。
接下来有n行每一行分别有两个整数Ai,Bi(Ai<=Bi)，代表第i艘游轮的到达和离开时间。
所有船只的到达和离开时间都不会相等。
輸出說明
：
请输出能让所有船只靠岸的最少码头数。
範例輸入 ：
4 1 30 5 10 6 12 11 20
範例輸出 ：
2
提示
：
占总分30%的测试数据中n<=15
占总分100%的测试数据中n<=1000，并且所有数字皆不超过1000000000。
占总分100%的测试数据中n<=1000，并且所有数字皆不超过1000000000。
出處
：
CSAPC'08 Problem Setter: Seanwu
原本的題解, 請自行點閱。百度真的存在一堆大神
我就稍微翻譯一下, 我們先將問題做個轉換
如果兩條船不能在同一個港口停，則AI<AJ<BI<BJ 就將 I,J兩點建立一條邊，這樣可以得到一個圖，問題等價於求最少用幾個**分圖中的點使得各個**中没有任何兩點存在邊。
註解 : **分圖, 應該可以解釋, 用最少個集合, 而每個集合中的任意兩點不會相連, 或者可以理解成最小著色數
定義 ： 一個完全多邊形是 指 圖中的一個多邊形的任何兩點的連線都在圖中以邊的形式存在。
經過猜想，發現 最少**數P即圖中的最大完全多邊形邊數。
註解 : 因為這個最大完全多邊形 (或者可以理解成完美圖), 必然全部都要使用不同的顏色去圖。因此最大的完美圖等價於最小著色數
而這 P 個點滿足 AI<AJ<AK<....<AM<BI<BJ<BK<..<BM 。
反之我們只要求 滿足AI<AJ<AK<....<AM<BI<BJ<BK<..<BM 這樣的 數列中元素個數最多多少個
因此我使用 DP 去求這個數列最長為多少, 先窮舉 AI, BI, 然後再進行 LIS 的計算, 最慘 O(N^3)
有興趣的人可以去查查 "弧圖的最小著色數", 這題感覺不是區間圖, 因為可以包在裡面, 不過那個弧圖的觀念我弄不懂, 同時要使用什麼 "完美消去序列" 什麼的, 有興趣的人幫我補吧 !
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int a, b;
} Te;
Te B[1000];
int cmp(const void *i, const void *j) {
static Te *a, *b;
a = (Te *)i, b = (Te *)j;
return a->a - b->a;
}
int main() {
int n, i, j, k;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d %d", &B[i].a, &B[i].b);
qsort(B, n, sizeof(Te), cmp);
int ans = 0;
for(k = 0; k < n; k++) {
if(n-k < ans) break;
int dp[1000] = {};
dp[k] = 1;
for(i = k; i < n; i++) {
if(dp[i])
for(j = i+1; j < n; j++) {
if(B[j].a < B[k].b && B[j].b > B[i].b && dp[i]+1 > dp[j]) {
dp[j] = dp[i]+1;
}
if(B[j].a > B[k].b) break;
}
if(dp[i] > ans) ans = dp[i];
}
}
printf("%d\n", ans);
}
return 0;
}
原本的題解, 請自行點閱。百度真的存在一堆大神
我就稍微翻譯一下, 我們先將問題做個轉換
如果兩條船不能在同一個港口停，則AI<AJ<BI<BJ 就將 I,J兩點建立一條邊，這樣可以得到一個圖，問題等價於求最少用幾個**分圖中的點使得各個**中没有任何兩點存在邊。
註解 : **分圖, 應該可以解釋, 用最少個集合, 而每個集合中的任意兩點不會相連, 或者可以理解成最小著色數
定義 ： 一個完全多邊形是 指 圖中的一個多邊形的任何兩點的連線都在圖中以邊的形式存在。
經過猜想，發現 最少**數P即圖中的最大完全多邊形邊數。
註解 : 因為這個最大完全多邊形 (或者可以理解成完美圖), 必然全部都要使用不同的顏色去圖。因此最大的完美圖等價於最小著色數
而這 P 個點滿足 AI<AJ<AK<....<AM<BI<BJ<BK<..<BM 。
反之我們只要求 滿足AI<AJ<AK<....<AM<BI<BJ<BK<..<BM 這樣的 數列中元素個數最多多少個
因此我使用 DP 去求這個數列最長為多少, 先窮舉 AI, BI, 然後再進行 LIS 的計算, 最慘 O(N^3)
有興趣的人可以去查查 "弧圖的最小著色數", 這題感覺不是區間圖, 因為可以包在裡面, 不過那個弧圖的觀念我弄不懂, 同時要使用什麼 "完美消去序列" 什麼的, 有興趣的人幫我補吧 !
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int a, b;
} Te;
Te B[1000];
int cmp(const void *i, const void *j) {
static Te *a, *b;
a = (Te *)i, b = (Te *)j;
return a->a - b->a;
}
int main() {
int n, i, j, k;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d %d", &B[i].a, &B[i].b);
qsort(B, n, sizeof(Te), cmp);
int ans = 0;
for(k = 0; k < n; k++) {
if(n-k < ans) break;
int dp[1000] = {};
dp[k] = 1;
for(i = k; i < n; i++) {
if(dp[i])
for(j = i+1; j < n; j++) {
if(B[j].a < B[k].b && B[j].b > B[i].b && dp[i]+1 > dp[j]) {
dp[j] = dp[i]+1;
}
if(B[j].a > B[k].b) break;
}
if(dp[i] > ans) ans = dp[i];
}
}
printf("%d\n", ans);
}
return 0;
}