# CFR 510 D. Fox And Jumping ( DP )

Problem - D - Codeforces

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;
}
```