# TIOJ 1014. 打地鼠
###### tags: `Ans`

### 轉移式

* `dp[s][i]`
* s 代表地鼠的狀態, 如果第 x 位是 1 代表第x支還活着
* i 代表最後是敲下哪一個位置的地鼠(結尾)
* `dp[s][i] = min{ 0<=k<n | dp[在敲i之前][k結尾]+行走時間+一段時間到t[i]的倍數 }`
* 因爲地鼠是有週期性的, 所以值還要在加上一段時間變成週期的倍數

* $dp(s,i) = min\{r\ |\ 0\leq k<n,\ r=([(dp(s\&~(1<<i),k)+abs(i-k)]-1)/t[i]+1)*t[i]\}$
* $[(dp(s\&~(1<<i),k)+abs(i-k)]$
* 在敲 i 之前, 最後一個敲 k 的時間 + 從 k 跑到 i 的時間
* $((x-1)/t[i]+1)*t[i]$
* 把 x 變成 t[i] 的倍數 m, m>=x
* (x/t[i]+1)*t[i] 後小數點會被去掉加 1 再把 t[i] 乘回去, 能把他轉成 t[i] 的倍數
* 考慮 x 爲 t[i] 倍數的情況, 最後答案會太大
* 先把 x 減 1

### 實作
採用 bottom-up, 考慮要如何枚舉狀態
觀察到 `s~(1<<k)` 的部分, 一定小於等於 s
把 s 從小開始枚舉

當決定了 s, 該決定 i
注意 i 的意思是 s 的最後一個敲的地方, 所以必須保證 `s&(1<<i)`

### 邊界條件, 初始化
因爲 dp 要取 min, 所以一開始全部設成 INF

* 邊界設定有兩種方法

for (int i=0; i<n; i++)
    dp[1<<i][i] = t[i];

dp[0][0] = 1;
// 一開始站在第0個左邊, 要花 1 走第 0
// 決定了這個狀態後 s 從 1 開始枚舉
// 可以發現第一種邊界設定的狀態都可以繼續轉移來這裏

### CODE

#include <iostream>
#include <cstring>
using namespace std;
const int N = 16;

int dp[N][1<<N], t[N], n;

int main()
{
    cin >> n;
    for (int i=0; i<n; i++)
        cin >> t[i];
    
    memset(dp,0x7f,sizeof(dp));
    dp[0][0] = 1;
    
    for (int s=1; s<(1<<n); s++)
        for (int i=0; i<n; i++)
            if (s&(1<<i))
                for (int k=0,x; k<n; k++)
                    x = dp[k][s&~(1<<i)] + abs(k-i),
                    dp[i][s] = min( dp[i][s],((x-1)/t[i]+1)*t[i]);
                
                    
    int res = 0x7f7f7f7f;
    for (int i=0; i<n; i++)
        res = min( res, dp[i][(1<<n)-1]);
    cout << res << '\n';
}