[CSAPC][dp解] b178. 遊輪 Boat＠Morris' Blog｜PChome Online 個人新聞台

2012-09-25 08:26:47| 人氣879| 回應0 | 上一篇 | 下一篇

[CSAPC][dp解] b178. 遊輪 Boat

推薦 0 收藏 0 轉貼0 訂閱站台

埃及的尼罗河上有很多游轮，虽然可能分别属于不同的公司，但之间有个不成文的默契。当多艘游轮要靠岸时，一种可能是直接停靠在岸边的码头，另一种方式是靠在已经就位的船旁边。它们可以一艘接着一艘并排起来，离岸较远的船上的游客若要下船，则可以通过其它的船到达岸上。不过有个限制，就是离岸较近的船不可以比离岸较远的船先离开，不然就会被卡住出不去了。

给所有船只的到达和离开时间，问岸边最少需要几个码头，才能让所有的船有办法靠岸。

輸入說明：

输入的第一行有一个整数n，代表游轮的个数。
接下来有n行每一行分别有两个整数Ai,Bi(Ai<=Bi)，代表第i艘游轮的到达和离开时间。
所有船只的到达和离开时间都不会相等。

輸出說明：

请输出能让所有船只靠岸的最少码头数。

範例輸入：

範例輸出：

提示：

占总分30%的测试数据中n<=15
占总分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;
}

我要檢舉

#b178#遊輪 Boat#CSAPC'08#CSAPC

台長： Morris

您可能對以下文章有興趣

a250. NCPC2011 Problem H Special Subsequences

a094. NOI2003 Day1.1.木棒游戏

[ZJ] d372. 4. 合法執行路徑問題

b113. 6. 線性系統求解

人氣(879) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][heap+計算] a373. 賽車
此分類上一篇:[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

回應(0)