2011-07-20 11:45:13Morris
a192. 接線問題
a192. 接線問題
/* Problem: a192 "接線問題" from */
/* Language: C */
/* Result: AC (356ms, 276KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-20 10:58:19 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MaxV 2147483647
main() {
int U, L, a, b, c;
int IU[1000], IL[1000];
while(scanf("%d %d", &U, &L) == 2) {
for(a = 0; a < U; a++)
scanf("%d", &IU[a]);
for(a = 0; a < L; a++)
scanf("%d", &IL[a]);
int Min1[1000] = {}, Min2[1000] = {}, tmin = 0;
for(a = 0; a < U; a++) {
for(b = a, c = L-(U-a); b <= c; b++) {
Min2[b] = abs(IU[a]-IL[b]) + tmin;
tmin = (tmin < Min1[b]) ? tmin : Min1[b];
}
for(b = a; b <= c; b++)
Min1[b] = Min2[b];
tmin = Min1[a];
}
for(a = U-1, tmin = MaxV; a < L; a++)
tmin = (tmin < Min1[a]) ? tmin : Min1[a];
printf("%d\n", tmin);
}
return 0;
}
內容 ：
現在有兩排插孔, 必須將上面那一排的插孔, 全部接線到下面那一排去
而每個線的成本恰好是插孔與插孔的位置差的絕對值
現在給你這兩排插孔的位置, 請問最小成本
輸入說明
：
有多組測試資料, 每組第一行有兩個正整數 U, L (1 ≦ U ≦ L ≦ 1000)
接下來有兩行
第一行上有 U 個數字, 每個數字由小排到大, 且小於 2147483647
第一行上有 L 個數字, 每個數字由小排到大, 且小於 2147483647
輸出說明
：
對每一組輸出最小成本
範例輸入 ：
4 7 5 6 7 8 1 2 6 9 10 12 13
範例輸出 ：
7
提示
：
範例測資 其中一種的最小成本3+0+2+2 = 7
× 測資有誤, 或者題目重複, 請通知我 謝謝
出處
：
(管理：morris1028)
作法 : DP
首先, 你要先證明交叉的情況不會產生最佳解, 比較容易理解這個 DP
所謂的交叉情況
例如 5 接 6, 6 接 2, 這種情況不會是最佳解
我的直覺是這麼告訴我的, 所以我不會證明
那麼知道了這個結果後, 現在就開始來做 DP
假設 DP[X], L[l], U[u]
DP[X]儲存當前的接頭, 有最右邊在U[X]的最小值
NewDP[X] = min((L[y] - U[X]) + DP[0~X-1])
y 從 0 開始代到 l
其實不是很好說明, 作法是 O (N^2)
/**********************************************************************************/作法 : DP
首先, 你要先證明交叉的情況不會產生最佳解, 比較容易理解這個 DP
所謂的交叉情況
例如 5 接 6, 6 接 2, 這種情況不會是最佳解
我的直覺是這麼告訴我的, 所以我不會證明
那麼知道了這個結果後, 現在就開始來做 DP
假設 DP[X], L[l], U[u]
DP[X]儲存當前的接頭, 有最右邊在U[X]的最小值
NewDP[X] = min((L[y] - U[X]) + DP[0~X-1])
y 從 0 開始代到 l
其實不是很好說明, 作法是 O (N^2)
/* Problem: a192 "接線問題" from */
/* Language: C */
/* Result: AC (356ms, 276KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-20 10:58:19 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MaxV 2147483647
main() {
int U, L, a, b, c;
int IU[1000], IL[1000];
while(scanf("%d %d", &U, &L) == 2) {
for(a = 0; a < U; a++)
scanf("%d", &IU[a]);
for(a = 0; a < L; a++)
scanf("%d", &IL[a]);
int Min1[1000] = {}, Min2[1000] = {}, tmin = 0;
for(a = 0; a < U; a++) {
for(b = a, c = L-(U-a); b <= c; b++) {
Min2[b] = abs(IU[a]-IL[b]) + tmin;
tmin = (tmin < Min1[b]) ? tmin : Min1[b];
}
for(b = a; b <= c; b++)
Min1[b] = Min2[b];
tmin = Min1[a];
}
for(a = U-1, tmin = MaxV; a < L; a++)
tmin = (tmin < Min1[a]) ? tmin : Min1[a];
printf("%d\n", tmin);
}
return 0;
}