題目連結: https://tioj.ck.tp.edu.tw/problems/1014
# 內容
有 n 個從左而右排成一列的地鼠洞，相鄰兩個洞距離皆為 1。在每個洞各有一出現周期固定的地鼠，且地鼠被打一次之後就不會再出現。你在第一個洞的左邊距離 1 處，你每秒可走 1 的距離。現在給你每個地鼠的周期，求若要打完所有地鼠至少要花多久？
# 思路
dp[s][i]
- s 代表地鼠的狀態，如果第 x 位是 1 代表第 x 支還活着
- i 代表最後是敲下哪一個位置的地鼠 (結尾)
dp[s][i] = min{ 0<=k<n | dp[在敲i之前][k結尾]+行走時間+一段時間到t[i]的倍數 }
轉換 (進位) 為倍數的方式有兩種:
- time -1 就是擔心 time 本身就是 T [i] 的倍數
- (ceil 就是無條件進位)
# 程式碼
#include<bits/stdc++.h> | |
#define INF 999999999 | |
using namespace std; | |
int dp[(1<<16)][17],T[17],ans,n; | |
int main() | |
{ | |
ios_base::sync_with_stdio(0); cin.tie(0); | |
cin >> n; | |
for(int i = 0; i < n; i++) cin >> T[i]; | |
fill(&dp[0][0],&dp[1<<n][n],INF); ans = INF; | |
dp[0][0] = 1; | |
for(int s = 1; s < (1<<n); s++) | |
for(int i = 0; i < n; i++) { | |
if(!(s&(1<<i))) continue; // 已經被打死了 QQ | |
for(int j = 0; j < n; j++) { | |
int time = dp[s&~(1<<i)][j]+abs(j-i); // 原本 + 移動至 i | |
int p = ceil((double)time/ T[i] )* T[i]; // 等待至整數倍 | |
dp[s][i] = min(dp[s][i],p); | |
} | |
if(s == (1<<n)-1) ans = min(ans,dp[s][i]); | |
} | |
cout << ans << '\n'; | |
} |
