[ZJ][dp] a449. 國王烏龜的接駁車＠Morris' Blog

2012-09-29 09:28:31| 人氣1,149| 回應0 | 上一篇 | 下一篇

[ZJ][dp] a449. 國王烏龜的接駁車

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

內容：

本題來自 TIOJ 1623

烏龜國王開放讓百姓去覲見他，舉國上下無一不期待能一睹國王的真面目。

於是，n 隻烏龜便排成一列等著搭上直達皇宮的專車。

然而，搭往皇宮的專車只有k 班，而每台車重量負荷都一樣是m 公斤。

現在依序給你每隻烏龜的重量wi，

依序每支烏龜走過來時，車長只能決定叫他立刻上車或是把他踢開，

然後當那隻烏龜上去會超過該台車的負重時那班車就會開走，下一班會立刻過來。

當然國王希望越多隻烏龜能見到他越好，

他想問你，最多能有幾隻烏龜搭上車？

輸入說明：

第一行包含三個數字n, k, m。

第二行有n個數字wi，表示從隊伍前端到隊伍末端的烏龜重量。

1 <= n, k <= 2,000;
1 <= m <= 10,000,000;
1 <= wi <= 10,000;

輸出說明：

輸出含一個數字n，表示最多能讓幾隻烏龜搭上車。

範例輸入：

5 2 10
5 8 12 3 5

範例輸出：

提示：

烏龜系列前傳。

測資是我自己出的，如果有誤麻煩通知一下 ><

通過了可以去TIOJ 1623 測試本題

因為只有一筆測資，所以封鎖答案!

出處：

USACO`96 Problem setter: ATP TIOJ 1623 (管理：stanley17112000)

dp[i] 表示可以裝 i 隻烏龜的情況, 那麼 dpc[i] 代表裝 i 隻需要幾輛公車, dpw[i] 代表此時的公車負重,

那麼我們可以知道 dpc[i] 越小越好, dpw[i] 越小越好

#include <stdio.h>

int main() {
    int n, k, m;
    while(scanf("%d %d %d", &n, &k, &m) == 3) {
        int i, j, wi;
        int dpc[2005] = {}, dpw[2005] = {};
        for(i = 1; i <= n; i++)
            dpc[i] = n+1, dpw[i] = 0xffffff;
        dpc[0] = 1, dpw[0] = 0;
        for(i = 0; i < n; i++) {
            scanf("%d", &wi);
            if(wi > m) continue;
            for(j = i; j >= 0; j--) {
                if(dpw[j] + wi > m) {
                    if(dpc[j]+1 < dpc[j+1] || (dpc[j]+1 == dpc[j+1] && wi < dpw[j+1])) {
                        if(dpc[j]+1 > k)    continue;
                        dpc[j+1] = dpc[j]+1, dpw[j+1] = wi;
                    }
                } else {
                    if(dpc[j] < dpc[j+1] || (dpc[j] == dpc[j+1] && dpw[j]+wi < dpw[j+1]))
                        dpc[j+1] = dpc[j], dpw[j+1] = dpw[j]+wi;
                }
            }
        }
        i = n;
        while(dpc[i] == n+1)    i--;
        printf("%d\n", i);
    }
    return 0;
}

我要檢舉

#a449#國王烏龜的接駁車

台長： Morris

您可能對以下文章有興趣

d828. Pascal's triangle's secret (II)

[ZJ] a473. 外援計畫

d624. 燈泡問題

[ZJ][bfs, dfs] a634. 14. Knights Path

人氣(1,149) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][逆元、降階、高斯、短碼] a542. 行列式det(A)
此分類上一篇:[ZJ][數學解] a532. 奇特的數列

回應(0)