[TIOJ] 1014打地鼠

題目連結：http://tioj.ck.tp.edu.tw/problems/1014
　　看來是我輕忽了，以前是看別人的code才會寫的，現在想想位元DP我從來好像也只寫過這麼一題而已QQ，我因為這題今天差點陷入低潮，一直錯、懷疑自己之類的，中途還差點想要去看解，不過最後守著最後一絲堅持送上去之後出乎意料的AC了XD。
　　不靠自己解出這題不行，我必須變得更強！
　　如果知道位元DP的觀念的話很容易寫出轉移式：dp[s][i] = dp[s/i][j]+abs(j-i)+@@@，由於每隻地鼠都有一定的周期才會出來，所以到i隻的時間就必須要是T[i]的倍數，這裡就必須動點腦筋了，我的寫法是dp[s][i] = ceil((dp[s/i][j]+abs(j-i))/T[i])*T[i]，不過網路上其他人的寫法則是((dp[s/i][j]+abs(j-i)-1)/T[i]+1)*T[i]。
　　另外，設定邊界dp[0][0] = 1，之後會比較好處理，算是一種熟悉位元DP的人能夠信手拈來的技巧吧，但是我一開始沒想到就去算了dp[1<<i][i]當作邊界了QQ
　　看來我還有很多技巧要學！！

#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;
            for(int j = 0; j < n; j++)
            {
                int tt = dp[s-(1<<i)][j]+abs(j-i);
                int p = ceil((double)tt/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';
}