TOIJ 1014 打地鼠 ( bitset DP )

1014 - 打地鼠 | TIOJ INFOR Online Judge
挺水的。O( ( n ^ 2 ) * ( 2 ^ n ) )

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 16 + 2;
const int MAXA = 1e8 + 8;
const int INF = 2e9;

int n;
int a[ MAXN ];

int dp[ MAXN ][ 1 << MAXN ]; // last hit hole / hit set

void upmin(int &x, int v){
    if( x > v ) x = v;
}

int ab(int x){ return x < 0 ? -x : x; }

int getTime(int t, int f){
    if( f > t ) return f;
    return f * ( ( t + f - 1 ) / f );
}

void solve(){
    for(int i = 0; i < n; ++i)
        for(int S = 0; S < ( 1 << n ); ++S)
            dp[ i ][ S ] = INF;
    for(int i = 0; i < n; ++i)
        dp[ i ][ 1 << i ] = a[ i ];
    for(int S = 1; S < ( 1 << n ) - 1; ++S){
        for(int i = 0; i < n; ++i)
            if( ( S >> i ) & 1 )
                for(int j = 0; j < n; ++j)
                    if( !( ( S >> j ) & 1 ) ){
                        upmin( dp[ j ][ S | ( 1 << j ) ], getTime( dp[ i ][ S ] + ab( i - j ), a[ j ] ) );
                    }
    }
    int ans = INF;
    for(int i = 0; i < n; ++i)
        ans = min<int>( ans, dp[ i ][ ( 1 << n ) - 1 ] );
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[ i ]);
    solve();
    return 0;
}