【題解】TIOJ 1014 . 打地鼠

#include <iostream>
using namespace std;

int n, s[20];
long long dp[1<<16][16], ans;

long long f(long long mask, int pos){
    if (dp[mask][pos]) return dp[mask][pos];
    long long msk = mask ^ (1<<pos);
    if (!msk){
        dp[mask][pos] = (pos/s[pos]+1)*s[pos];
        return dp[mask][pos];
    }
    long long mn = 1e18;
    for (int i = 0; i < n; i++){
        if (!(msk&(1<<i))) continue;
        long long ret = f(msk, i);
        long long time = ret + abs(pos-i);
        time = ((time-1)/s[pos]+1)*s[pos];
        mn = min(mn, time);
    }
    dp[mask][pos] = mn;
    return dp[mask][pos];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s[i];
    }
    ans = 1e18;
    for (int i = 0; i < n; i++){
        ans = min(ans, f(((1<<n)-1), i));
    }
    cout << ans << "\n";
}