Submission #00002
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <bits/stdc++.h> using namespace std; #define long long long #define itn int itn n, m; int cnt[20]; int d[100100]; int dp[1<<21]; int WA_tle[100100][20]; int getPos ( int bit ) { itn ans = 0; for ( int i = 0; i < m; i++ ) { if ( (1<<i) & bit ) { ans += cnt[i]; } } return ans; } int getWA ( int start, int end, int target ) { int ans = 0; for ( int j = 0; j < m; j++ ) { if ( target != j ) { ans += WA_tle[end][j] - WA_tle[start][j]; } } return ans; } int dfs ( int bit ) { if ( ~dp[bit] ) return dp[bit]; int pos = getPos(bit); if ( pos == n ) return 0; int rec = 0x3f3f3f3f; for ( int i = 0; i < m; i++ ) { if ( ! ( (1<<i) & bit ) ) { int auf = pos + cnt[i]; int wa = getWA ( pos, auf, i ); rec = min ( rec, dfs ( bit | (1<<i) ) + wa ); } } return dp[bit] = rec; } signed main ( ) { cin >> n >> m; for ( int i = 0; i < n; i++ ) { cin >> d[i]; d[i]--; cnt[d[i]]++; for ( int j = 0; j < m; j++ ) { WA_tle[i+1][j] = WA_tle[i][j] + ( j == d[i] ); } } memset (dp, -1, sizeof (dp)); cout << dfs ( 0 ) << endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0001 - ぬいぐるみの整理 (Plush Toys) |
ユーザー名 | r1825 |
投稿日時 | 2019-12-04 16:21:42 |
言語 | C++14 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 1344 Byte |
最大実行時間 | 226 ms |
最大メモリ使用量 | 16888 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | set1 | 20 / 20 | *t4*1.txt |
2 | set2 | 20 / 20 | *t4*2.txt |
3 | set3 | 20 / 20 | *t4*3.txt |
4 | set4 | 20 / 20 | *t4*4.txt |
5 | set5 | 20 / 20 | *t4*5.txt |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # | ||||
---|---|---|---|---|---|---|---|---|
2017-yo-t4-in1.txt | AC | 28 ms | 10716 KB |
1
|
||||
2017-yo-t4-in2.txt | AC | 22 ms | 10812 KB |
2
|
||||
2017-yo-t4-in3.txt | AC | 29 ms | 16888 KB |
3
|
||||
2017-yo-t4-in4.txt | AC | 115 ms | 11080 KB |
4
|
||||
2017-yo-t4-in5.txt | AC | 226 ms | 16772 KB |
5
|