Bangladesh OI 2016 National Round pC. Counting Permutations ( DP )
http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces
題意:
求有多少 [ 1, N ] 的排列,有至少 K 個逆序數對。
資料規模:
For easy version: 1≤ N≤ 200 and 0≤ K≤ 300. [40% of total score]
For hard version: 1≤ N≤ 2000 and 0≤ K≤ 3000. [100% of total score]
TL: 1000 ms
ML: 256 MB
解法:
感覺可以 N * K 所以要考慮 DP。有時候要靠直覺。
dp[ n ][ k ] : [ 1, n ] 的排列中,有恰好 k 個逆序數對的排列數。
想一下加入新的元素 n + 1 的時候會如何轉移:
放在最後一個:轉移至 dp[ n + 1 ][ k ]
插在最後一個的前面:轉移至 dp[ n + 1 ][ k + 1 ]
插在由後面數第 i ( 1 base ) 個的前面:轉移至 dp[ n + 1 ][ k + i ]
所以有了狀態 O( N * K ),轉移 O( N ) 的東西。
寫成遞迴式:
dp[ n ][ k ] = Sigma{ dp[ n - 1 ][ i ], for all max( 0, k - ( n - 1 ) ) ≤ i ≤ k }
因為轉移需要的總是連續和,所以可以開另一個 dp 維護 dp 的前綴和。轉移變成 O( 1 )
時間 / 空間複雜度:
O( N * K )
void solve(){ int T; cin >> T; for( int kase = 1; kase <= T; ++kase ){ cout << "Case " << kase << ": "; int N, K; cin >> N >> K; int ans = 1; for( int i = 1; i <= N; ++i ){ ( ans *= i ) %= MOD; } if( K == 0 ){ cout << ans << endl; continue; } vvi dp( N + 1, vi( K ) ); vvi pdp( N + 1, vi( K + 1 ) ); dp[ 0 ][ 0 ] = 1; for( int i = 0; i < K; ++i ){ pdp[ 0 ][ i + 1 ] = pdp[ 0 ][ i ] + dp[ 0 ][ i ]; } for( int i = 1; i <= N; ++i ){ for( int j = 0; j < K; ++j ){ dp[ i ][ j ] = ( pdp[ i - 1 ][ j + 1 ] - pdp[ i - 1 ][ max( 0, j - ( i - 1 ) ) ] )% MOD; pdp[ i ][ j + 1 ] = ( pdp[ i ][ j ] + dp[ i ][ j ] ) % MOD; } } /* for( int i = 0; i < N; ++i ){ // slow version for( int j = 0; j < K; ++j ){ for( int k = 0; k <= i; ++k ){ if( j + k >= K ) continue; ( dp[ i + 1 ][ j + k ] += dp[ i ][ j ] ) %= MOD; } } } */ for( int i = 0; i < K; ++i ){ ( ans -= dp[ N ][ i ] ) %= MOD; } if( ans < 0 ) ans += MOD; cout << ans << endl; } }