題目敘述
隨著時間的腳步前進,打地鼠遊戲也不斷的翻新,最新一代的打地鼠遊戲不只測試你的反應能力,同時也考驗著你的體力和智力。地鼠基地是一個長型的基座,基座上每隔一公尺就會有一個地鼠洞,由左至右編號為 $1,2,\ldots,n$。玩家站在這個基地的最左邊,與第一個地鼠洞相距 $1$ 公尺;拿著一根鎚子,準備開始這個遊戲。編號為 $i$ 的地鼠洞每 $T_i$ 秒地鼠會出現一次。被打的地鼠不再出現,只要將所有地鼠打完,就結束遊戲,並且紀錄從開始到結束遊戲的秒數,越快越好。現在問題來了,負責製造這個地鼠基地的遊戲廠商想要知道結束遊戲所需的最少秒數,於是拜託你幫忙寫個程式來解決它。
假定玩家們的體力很好,隨時以每秒 $1$ 公尺的速度移動,並且不受移動方向改變的影響,打地鼠所花的時間也可以忽略不計。
輸入說明
第一行有一個數字 $n$,代表地鼠洞的數量 $(1\le n\le 16)$。第二行有 $n$ 個數字。所有數字皆不大於 $100,000,000$。
輸出說明
請輸出結束遊戲所需的最少秒數 $S$。
Sample Input
3
3 2 5
Sample Output
5
出處
95建中資訊培訓模擬試題一(Prob 6)
OJ連結
題解
這個題目是動態規劃,我們定義狀態 $\dp(S, i)$ 表示玩家已經打掉集合 $S\subseteq [n]$ 的地鼠,而且目前玩家所在位置是 $i$ 所需的最少秒數。
/* by tmt514 */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<string> forest = {
"*****************",
"*...*.......**..*",
"**..*....*.*.*..*",
"*......*.**.**.**",
"*..**...**..**.**",
"**.....**..*.*..*",
"*....*..........*",
"*.....****.*...**",
"****.*.*........*",
"*****************",
};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int onFire[10][17];
int onEscape[10][17];
void bfs(int mark[10][17], int hasFire[10][17], int sx, int sy, int T) {
queue<int> q;
// 如果一開始就著火了,就應該直接死掉。
if (hasFire && hasFire[sx][sy] <= T) return;
mark[sx][sy] = T;
q.push(sx);
q.push(sy);
while (!q.empty()) {
int x = q.front(); q.pop();
int y = q.front(); q.pop();
int t = mark[x][y];
// 依序考慮四個方向是否可通行,如果可通行的話加到佇列裡面。
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (forest[nx][ny] == '.' &&
mark[nx][ny] == 0 &&
(!hasFire || hasFire[nx][ny] == 0 || hasFire[nx][ny] > t+1)) {
mark[nx][ny] = t+1;
q.push(nx);
q.push(ny);
}
}
}
}
int main() {
int fx, fy, sx, sy, ex, ey, T;
cin >> fx >> fy >> T;
cin >> sx >> sy >> ex >> ey;
// 由於火勢不會燒到避難處,所以一開始要取巧把這格改掉。
forest[ex][ey] = 'E';
bfs(onFire, NULL, fx, fy, 1);
// 然後把它改回變成可以通行。
forest[ex][ey] = '.';
bfs(onEscape, onFire, sx, sy, T);
if (onEscape[ex][ey] > 0) {
cout << onEscape[ex][ey]-T << endl;
} else {
cout << "Help!" << endl;
}
return 0;
}
關於這題
第一次嘗試出的位元壓縮 DP,相當地有趣呢。