2012-09-29 09:28:31Morris
[ZJ][dp] a449. 國王烏龜的接駁車
內容 ：
本題來自 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
範例輸出 ：
3
提示
：
烏龜系列前傳。
測資是我自己出的，如果有誤麻煩通知一下 ><
通過了可以去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;
}
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;
}