Submission #10944

ソースコード

?
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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#define F first
#define S second
using namespace std;
int n,m;
int a[111111];
int sa[22][111111];
int aa[22];
int dp[1<<22];
int solve(int bit,int s){
if(bit == (1<<m)-1) return 0;
if(dp[bit] >= 0) return dp[bit];
int ret = 1<<28;
for(int i = 0; i < m; i++){
if(bit & (1<<i)) continue;
ret = min(ret,aa[i]-(sa[i][s+aa[i]]-sa[i][s])+solve(bit|(1<<i),s+aa[i]));
}
return dp[bit] = ret;
}
int main(void){
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%d",a+i);
a[i]--;
sa[a[i]][i] = 1;
}
for(int j = 0; j < m; j++){
for(int i = 1; i <= n; i++){
sa[j][i] += sa[j][i-1];
}
aa[j] = sa[j][n];
}
memset(dp,-1,sizeof(dp));
printf("%d\n",solve(0,0));
}

ステータス

項目 データ
問題 0595 - ぬいぐるみの整理 (Plush Toys)
ユーザー名 ei1133
投稿日時 2016-12-11 16:47:49
言語 C++11
状態 Accepted
得点 1
ソースコード長 955 Byte
最大実行時間 127 ms
最大メモリ使用量 25988 KB

セット

セット 得点 Cases
1 set1 20 / 20 *t4*1.txt
2 set2 0 / 20 *t4*2.txt
3 set3 0 / 20 *t4*3.txt
4 set4 0 / 20 *t4*4.txt
5 set5 0 / 20 *t4*5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2017-yo-t4-in1.txt AC 24 ms 18912 KB
1
2017-yo-t4-in2.txt AC 24 ms 21204 KB
2
2017-yo-t4-in3.txt AC 32 ms 23484 KB
3
2017-yo-t4-in4.txt AC 65 ms 25124 KB
4
2017-yo-t4-in5.txt AC 127 ms 25988 KB
5