2012-09-11 21:08:48Morris
[ZJ版本][dp] d524. Q10599 - Robots(II)
內容 ：
你 所任職的公司專門製造用來撿垃圾的機器人，每當機器人被指派到一個工作前，會先把場地的配置圖轉成網格輸入到電腦中，每個場地可以視為一平面，在圖上會標 出所有垃圾所在的格子。機器人會從最西北角的格子開始走，走到最東南角的格子為止，然而在每一次的移動中只能向東或南方移動一格。
機器人會沿著格子把垃圾蒐集起來，直到到達終點所在的最東南方格子，便不能再被重新利用。基於所用的花費將會與機器人數成正比，你對於「如何最有效率的使用」之類的問題感興趣，因此，你的任務便是要用單一一個機器人經過的路徑上蒐集最多的垃圾數。
當然符合這樣條件的路徑就會有許多種，你的程式便必須輸出總共有幾條這樣的路徑會撿到最多的垃圾數。你的機器人能不占任何空間的清除路上所及的垃圾.一組合法的路徑輸出將會是沿路上所經之垃圾格子的編號順序.雖然你的機器人不能清除不包含垃圾的格子,但若你希望的話,你能設定你的機器人經過某些特定的點但不清除其上的垃圾.
上圖為一6x7的網格，格子從左往右、從上到下依序編號1、2、3、4、……、42，上圖範例的最大垃圾收集數為5並有4種不同的可行路徑包含:<2, 4, 11, 13, 28><2, 4, 11, 13, 41><2, 4, 11, 25, 28><2, 4, 11, 25, 41>
其中編號2,4,11,13,25,28,41對應平面座標(1,2),(1,4),(2,4),(2,6),(4, 4),(4, 7),(6, 7)的格子點
輸入說明
：
每組輸入為一場地配置圖,第一行為一對整數表示場地
的大小n和m(n,m<=100),讀到-1,-1表結束輸入,接下來的幾行會有多對的整數,每兩個整數自成一行表示被垃圾佔據的格子座標,讀到
0,0即為表對一張場地配置圖的描述結束,且同一個點不會被重複標記成包含垃圾兩次或兩次以上.
輸出說明
：
對於每一組測資先輸出數字對應第幾組的輸入，接著輸出整數代表機器人所能收集的最大垃圾數K，及所有能收集該垃圾數的路徑數，皆下來的K個整數請列舉出其中任意一種的可行路徑。上述任兩個整數間皆以一個空白格開。ps:由於出題者本身不會用SPECIAL JUDGE的緣故,在ZERO JUDGE submit時就直接輸出:CASE#輸出序號:最大蒐集數<空格>總路徑數<換行>
&&答案中任意一數都不會超過2147483647
範例輸入
：
6 7 1 2 1 4 2 4 2 6 4 4 4 7 6 6 0 0 4 4 1 1 2 2 3 3 4 4 0 0 -1 -1
範例輸出 ：
CASE#1: 5 4 CASE#2: 4 1
提示
：
(1)aDorable Panda
(2)Delicious Pancake
(3)Damn Panchiao senior high school
2010/5/28偷偷的加強了測資~~(敬請見諒
出處
：
UVA online judge 10599
(管理：pcshic)
#include <stdio.h>
#include <stdlib.h>
#define min(x,y) ((x)<(y)?(x):(y))
typedef struct {
int x, y;
} Pt;
int cmp(const void *i, const void *j) {
Pt *x, *y;
x = (Pt *)i, y = (Pt *)j;
if(x->x != y->x)
return x->x - y->x;
return x->y - y->y;
}
int main() {
int n, m, cases = 0, i, j, k;
int x, y;
while(scanf("%d %d", &n, &m) == 2) {
if(n < 0 && m < 0) break;
int idx = 0, used[105] = {}, ut = -1;
int cnt[105] = {}, hd[105], map[105][105];
Pt A[10005];
int dp[10005][2] = {};
while(scanf("%d %d", &A[idx].x, &A[idx].y) == 2) {
if(!A[idx].x && !A[idx].y) break;
used[A[idx].x] = 1;
cnt[A[idx].x]++;
idx++;
}
for(i = 1; i <= n; i++) {
if(used[i] == 1) {
used[++ut] = i;
}
hd[i] = 0xffff;
}
qsort(A, idx, sizeof(Pt), cmp);
for(i = 0; i < idx; i++)
hd[A[i].x] = min(hd[A[i].x], i);
int top = -1;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(top+1 < idx && i == A[top+1].x && j == A[top+1].y)
top++;
map[i][j] = top;
}
}
int st, ed, sk, k2;
for(st = 0; st <= ut; st++) {
i = used[st];
for(k = hd[i], sk = 0; sk < cnt[i]; k++, sk++) {
for(ed = st; ed >= 0; ed--) {
j = used[ed];
for(k2 = map[j][A[k].y]; k2 >= hd[j]; k2--) {
if(A[k].x == A[k2].x && A[k].y == A[k2].y)
continue;
if(dp[k][0] < dp[k2][0]+1)
dp[k][0] = dp[k2][0]+1, dp[k][1] = 0;
if(dp[k][0] == dp[k2][0]+1)
dp[k][1] += dp[k2][1];
break;
/*printf("%d %d - %d %d\n", A[k].x, A[k].y, A[k2].x, A[k2].y);*/
}
}
if(dp[k][0] == 0) dp[k][0] = 1, dp[k][1] = 1;
}
}
int ans = 0, way = 0;
for(i = 0; i < idx; i++) {
/*printf("%d %d - %d %d\n", A[i].x, A[i].y, dp[i][0], dp[i][1]);*/
if(dp[i][0] > ans)
ans = dp[i][0], way = 0;
if(dp[i][0] == ans)
way += dp[i][1];
}
printf("CASE#%d: %d %d\n", ++cases, ans, way);
}
return 0;
}