[TIOJ] 1014. 打地鼠

題目連結:http://tioj.infor.org/problems/1014

---

n小小的，所以應該不難猜到這題可以狀態壓縮DP。狀態我這裡是寫$dp[S][i] = 已打S，且最後一個打的是i所需的最小時間$，那轉移就是$ dp[S][i] = \displaystyle \min_{j \in S-\{i\}}(dp[S-i][j] + |i-j| + (t[i] - ((dp[S-i][j] + |i-j|) \mod t[i])) \mod t[i]) $

#include <bits/stdc++.h>
using namespace std;
const int N = 16;
const int INF = 2000000000;

bool dped[(1<<N)+5][N+5];
int n, t[N+5];
int dp[(1<<N)+5][N+5];
int f(int,int);
bool inS(int,int);

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>t[i];
	for(int i=0;i<n;i++){
		dped[1<<i][i] = 1;
		dp[1<<i][i] = i+1 + (t[i]-((i+1)%t[i]))%t[i];
	}
	int ans=INF;
	for(int i=0;i<n;i++)
		ans = min(ans, f((1<<n)-1, i));
	cout<<ans<<'\n';
	return 0;
}

bool inS(int S, int e){
	return S & (1<<e);
}

int f(int S, int i){
	if(!dped[S][i]){
		dp[S][i] = INF;
		for(int j=0;j<n;j++) if(inS(S, j) && i!=j)
			dp[S][i] = min(dp[S][i], \
				f(S-(1<<i), j) + abs(i-j) + \
				((t[i]- ((dp[S-(1<<i)][j]+abs(i-j)) % t[i]))%t[i]) \
			);
		dped[S][i]=1;
	}
	return dp[S][i];
}