QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #28322 | #2945. 1's For All | hld67890# | AC ✓ | 91ms | 17692kb | C++17 | 1.2kb | 2022-04-13 16:04:00 | 2022-04-29 09:37:49 |
Judging History
answer
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int dp[120000];
vector < int > v[120000] , fac[120000];
void work () {
int i , j;
scanf ( "%d" , &n );
dp[1] = 1;
v[1].push_back ( 1 );
for ( i = 1 ; i <= n ; i++ ) {
for ( j = i ; j <= n ; j += i ) {
fac[j].push_back ( i );
}
}
for ( i = 2 ; i <= n ; i++ ) {
dp[i] = i;
for ( auto k : fac[i] ) {
if ( k != 1 && k != i ) {
dp[i] = min ( dp[i] , dp[k] + dp[i/k] );
}
}
int a = i % 10 , b = i / 10 , pw = 10 , ok;
if ( a == 0 ) ok = 0;
else ok = 1;
for ( ; b ; ) {
if ( ok == 1 ) {
dp[i] = min ( dp[i] , dp[a] + dp[b] );
//printf ( "%d %d %d\n" , i , a , b );
}
if ( b % 10 == 0 ) ok = 0;
else ok = 1;
a = a + pw * (b%10);
b = b / 10;
pw = pw * 10;
}
/*for ( j = 1 ; j < i ; j++ ) {
dp[i] = min ( dp[i] , dp[j] + dp[i-j] );
}*/
for ( j = 1 ; j * 2 <= dp[i] ; j++ ) {
for ( auto k : v[j] ) {
dp[i] = min ( dp[i] , dp[k] + dp[i-k] );
}
}
v[dp[i]].push_back ( i );
//if ( dp[i] <= 10 ) printf ( "%d %d\n" , i , dp[i] );
}
printf ( "%d\n" , dp[n] );
}
int main () {
work ();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 74ms
memory: 17552kb
input:
100000
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 73ms
memory: 16748kb
input:
90909
output:
13
result:
ok single line: '13'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9664kb
input:
10101
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 6ms
memory: 9652kb
input:
10001
output:
11
result:
ok single line: '11'
Test #5:
score: 0
Accepted
time: 76ms
memory: 17596kb
input:
99999
output:
11
result:
ok single line: '11'
Test #6:
score: 0
Accepted
time: 80ms
memory: 17528kb
input:
99998
output:
14
result:
ok single line: '14'
Test #7:
score: 0
Accepted
time: 77ms
memory: 17664kb
input:
99997
output:
13
result:
ok single line: '13'
Test #8:
score: 0
Accepted
time: 83ms
memory: 17524kb
input:
99989
output:
17
result:
ok single line: '17'
Test #9:
score: 0
Accepted
time: 74ms
memory: 17580kb
input:
99988
output:
16
result:
ok single line: '16'
Test #10:
score: 0
Accepted
time: 1ms
memory: 8880kb
input:
2
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 73ms
memory: 17692kb
input:
99984
output:
15
result:
ok single line: '15'
Test #12:
score: 0
Accepted
time: 91ms
memory: 17456kb
input:
98069
output:
18
result:
ok single line: '18'
Test #13:
score: 0
Accepted
time: 86ms
memory: 17328kb
input:
96721
output:
10
result:
ok single line: '10'
Test #14:
score: 0
Accepted
time: 56ms
memory: 14876kb
input:
70549
output:
18
result:
ok single line: '18'
Test #15:
score: 0
Accepted
time: 51ms
memory: 14424kb
input:
65621
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 27ms
memory: 12480kb
input:
44521
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 11ms
memory: 11364kb
input:
31111
output:
7
result:
ok single line: '7'
Test #18:
score: 0
Accepted
time: 15ms
memory: 10888kb
input:
21111
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 8ms
memory: 10484kb
input:
20158
output:
17
result:
ok single line: '17'
Test #20:
score: 0
Accepted
time: 9ms
memory: 9808kb
input:
11111
output:
5
result:
ok single line: '5'
Test #21:
score: 0
Accepted
time: 5ms
memory: 8864kb
input:
12
output:
3
result:
ok single line: '3'
Test #22:
score: 0
Accepted
time: 5ms
memory: 9540kb
input:
9609
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 7ms
memory: 9268kb
input:
5738
output:
15
result:
ok single line: '15'
Test #24:
score: 0
Accepted
time: 2ms
memory: 9052kb
input:
2087
output:
14
result:
ok single line: '14'
Test #25:
score: 0
Accepted
time: 5ms
memory: 8992kb
input:
1111
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 5ms
memory: 8916kb
input:
718
output:
13
result:
ok single line: '13'
Test #27:
score: 0
Accepted
time: 0ms
memory: 8748kb
input:
389
output:
12
result:
ok single line: '12'
Test #28:
score: 0
Accepted
time: 5ms
memory: 9060kb
input:
203
output:
11
result:
ok single line: '11'
Test #29:
score: 0
Accepted
time: 6ms
memory: 9148kb
input:
111
output:
3
result:
ok single line: '3'
Test #30:
score: 0
Accepted
time: 0ms
memory: 9064kb
input:
58
output:
10
result:
ok single line: '10'
Test #31:
score: 0
Accepted
time: 2ms
memory: 8704kb
input:
57
output:
9
result:
ok single line: '9'
Test #32:
score: 0
Accepted
time: 0ms
memory: 8980kb
input:
20
output:
8
result:
ok single line: '8'
Test #33:
score: 0
Accepted
time: 5ms
memory: 8904kb
input:
11
output:
2
result:
ok single line: '2'
Test #34:
score: 0
Accepted
time: 2ms
memory: 8880kb
input:
10
output:
7
result:
ok single line: '7'
Test #35:
score: 0
Accepted
time: 2ms
memory: 8932kb
input:
7
output:
6
result:
ok single line: '6'
Test #36:
score: 0
Accepted
time: 5ms
memory: 8800kb
input:
5
output:
5
result:
ok single line: '5'
Test #37:
score: 0
Accepted
time: 5ms
memory: 8696kb
input:
4
output:
4
result:
ok single line: '4'
Test #38:
score: 0
Accepted
time: 6ms
memory: 8812kb
input:
3
output:
3
result:
ok single line: '3'
Test #39:
score: 0
Accepted
time: 2ms
memory: 8812kb
input:
1
output:
1
result:
ok single line: '1'