CFR 510 D. Fox And Jumping ( DP )

Problem - D - Codeforces
題意：
給若干張卡片，每張卡片都有兩種屬性值，長度及價格。用相應的價格購買某張卡片後，可以擁有向左或向右跳對應的長度的次數不限的能力。求最小花費金額，使得可以跳到任意格子。
解法：
滿足可以跳到任意格子，等價於滿足所有卡片的長度的最大公因數為 1。考慮某個數 x，根據數據範圍≤ 1e9，其質因數至多 10個。
dp[ S ][ j ] : S 中的某位元代表 j 號卡片其對應編號的質數是否已被取消( 已取某其他卡片其長度不存在該質因數 )，有取 j 號卡片，此時的最小花費。

int N;
vi L;
vi C;

void init(){
    cin >> N;
    L = C = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> L[ i ];
    for( int i = 0; i < N; ++i )
        cin >> C[ i ];
    int g = 0;
    for( int i = 0; i < N; ++i )
        g = __gcd( g, L[ i ] );
    if( g > 1 ){
        cout << -1 << endl;
        exit( 0 );
    }
}

vvi fp;
vvi dp;

void preprocess(){
    fp = vvi( N );
    for( int i = 0; i < N; ++i ){
        int x = L[ i ];
        for( int j = 2; j * j <= L[ i ]; ++j )
            if( x % j == 0 ){
                fp[ i ].emplace_back( j );
                while( x % j == 0 )
                    x /= j;
            }
        if( x > 1 )
            fp[ i ].emplace_back( x );
    }
    dp = vvi( 1 << 10, vi( N, INF ) );
    for( int i = 0; i < N; ++i )
        dp[ 0 ][ i ] = C[ i ];
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < 1 << ( int ) fp[ i ].size(); ++j )
            for( int k = i + 1; k < N; ++k ){
                int b = 0;
                for( int l = 0; l < fp[ i ].size(); ++l )
                    if( not binary_search( fp[ k ].begin(), fp[ k ].end(), fp[ i ][ l ] ) )
                        b |= 1 << l;
                upmin( dp[ j | b ][ i ], dp[ j ][ i ] + C[ k ] );
            }
}

void solve(){
    int ans = INF;
    for( int i = 0; i < N; ++i )
        upmin( ans, dp[ max( 0, ( 1 << ( int ) fp[ i ].size() ) - 1 ) ][ i ] );
    cout << ans << endl;
}