2012-11-22 08:38:56Morris
[ZJ][dp] a491. 貨物集中問題
內容 ：
一個矩形平面大型倉儲空間，共有 R×C
個分區，其中 R 代表矩形的列數，C 代表矩形的行數。此倉儲空間以一 R×C
二維矩陣表示，倉儲空間中的每一分區以二維座標表示，二維矩陣中每一分區的內容代表各分區的儲存貨物量。今因整個倉儲空間保養維修的因素，需將所有分區的
貨物暫時集中於某一分區內，並假設任一分區的容量均可以容納目前倉儲空間中的總貨物容量。因為貨物移動需要移動成本，假定一個單位的貨物從現在的分區移動
到相鄰上下左右任意一個分區的成本為 100 元，請寫一程式決定貨物應該集中於那一分區，其整體移動成本為最小。
輸入說明
：
第一列有一個整數 N，代表測試資料有幾組。
第 二列有兩個數字 R, C, (1 <= R, C <= 2000)分別代表第一組測試資料的二維矩陣列數與行數。接下來的 R 列，每一列有 C 個整數，這 R 列中的第 i 列的第 j 個整數代表 (i, j) 區的儲存貨物量，且均 <=100000。每兩個整數之間都會有一個空白隔開。
輸出說明
：
第一列請輸出每一組測試資料貨物應該集中於那一分區 (i, j)，方能使其整體移動成本最小，以兩個整數表示，整數間以一個空白區隔。如有多個分區滿足條件，請輸出字典順序最小者。
第二列請輸出其所需要的最小成本。
範例輸入 ：
1 3 4 4 2 0 1 0 1 1 0 1 0 0 3
範例輸出 ：
1 2 2400
提示
：
請注意：
1. 原題測資 R, C <=100，與本題要求不盡相同。
2. ZJ 似乎會把換行吃掉，因此輸入格式並非如上所述。
出處
：
100 彰雲嘉區學科能力競賽資訊科
(管理：xavier13540)
最近的題目很愛玩優化輸入。
其實這個問題只求移動曼哈頓距離最少的 x, y 座標。
那麼 x y 可以分開討論，找到一個 x 位置最少移動成本。
同理對 y。可以用 O(n) 或者是 O(n^2) 解決都沒差。
反正輸入就是 O(n^2) 了，下面都是用 O(n)。
/**********************************************************************************/
/* Problem: a491 "貨物集中問題" from 100 彰雲嘉區學科能力競賽資訊科*/
/* Language: CPP (1478 Bytes) */
/* Result: AC(118ms, 295KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-20 16:35:22 */
/**********************************************************************************/
#include <stdio.h>
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int t, R, C, i, j, A;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &R, &C);
long long x[2001] = {}, y[2001] = {}, sum;
for(i = 1; i <= R; i++) {
for(j = 1, sum = 0; j <= C; j++) {
ReadInt(&A);
y[j] += A, sum += A;
}
x[i] = x[i-1] + sum;
}
for(i = 1; i <= C; i++)
y[i] += y[i-1];
int ax = 1, ay = 1;
long long ans, tmp = 0;
long long tot = 0;
for(i = 1; i <= R; i++)
tmp += (i-1)*(x[i]-x[i-1]);
ans = tmp;
for(i = 2; i <= R; i++) {
tmp = tmp + x[i-1] - (x[R]-x[i-1]);
if(tmp < ans)
ans = tmp, ax = i;
}
tot += ans, tmp = 0;
for(i = 1; i <= C; i++)
tmp += (i-1)*(y[i]-y[i-1]);
ans = tmp;
for(i = 2; i <= C; i++) {
tmp = tmp + y[i-1] - (y[C]-y[i-1]);
if(tmp < ans)
ans = tmp, ay = i;
}
tot += ans;
printf("%d %d\n%lld\n", ax, ay, tot*100);
}
return 0;
}
最近的題目很愛玩優化輸入。
其實這個問題只求移動曼哈頓距離最少的 x, y 座標。
那麼 x y 可以分開討論，找到一個 x 位置最少移動成本。
同理對 y。可以用 O(n) 或者是 O(n^2) 解決都沒差。
反正輸入就是 O(n^2) 了，下面都是用 O(n)。
/**********************************************************************************/
/* Problem: a491 "貨物集中問題" from 100 彰雲嘉區學科能力競賽資訊科*/
/* Language: CPP (1478 Bytes) */
/* Result: AC(118ms, 295KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-20 16:35:22 */
/**********************************************************************************/
#include <stdio.h>
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int t, R, C, i, j, A;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &R, &C);
long long x[2001] = {}, y[2001] = {}, sum;
for(i = 1; i <= R; i++) {
for(j = 1, sum = 0; j <= C; j++) {
ReadInt(&A);
y[j] += A, sum += A;
}
x[i] = x[i-1] + sum;
}
for(i = 1; i <= C; i++)
y[i] += y[i-1];
int ax = 1, ay = 1;
long long ans, tmp = 0;
long long tot = 0;
for(i = 1; i <= R; i++)
tmp += (i-1)*(x[i]-x[i-1]);
ans = tmp;
for(i = 2; i <= R; i++) {
tmp = tmp + x[i-1] - (x[R]-x[i-1]);
if(tmp < ans)
ans = tmp, ax = i;
}
tot += ans, tmp = 0;
for(i = 1; i <= C; i++)
tmp += (i-1)*(y[i]-y[i-1]);
ans = tmp;
for(i = 2; i <= C; i++) {
tmp = tmp + y[i-1] - (y[C]-y[i-1]);
if(tmp < ans)
ans = tmp, ay = i;
}
tot += ans;
printf("%d %d\n%lld\n", ax, ay, tot*100);
}
return 0;
}