KOI 2019 1차 고등부 2번 / 점프 - 17613
|
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
|
#include <iostream>
using namespace std;
int arr[31];
int getIdx(int u) {
int ret;
for(ret = 0; ret<31; ++ret)
if(arr[ret] > u) return ret-1;
}
int cal(int n) {
return 1+n*(n+1)/2;
}
int divide(int s, int e, int p) {
if(!s && !e) return p;
int idx;
int ne = e;
int ret = 0;
while(true) {
idx = getIdx(ne);
if(arr[idx] <= s) break;
if(arr[idx]*2 == ne) ret = max(ret, cal(idx));
else ret = max(ret, divide(0, ne-arr[idx], idx));
ne = arr[idx] - 1;
}
ret = max(ret, divide(s-arr[idx], ne-arr[idx], idx));
return ret + p;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int T; cin >> T;
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i<31; ++i)
arr[i] = 2*arr[i-1] + 1;
int u, v;
for(int tn = 0; tn<T; ++tn) {
cin >> u >> v;
cout << divide(u, v, 0) << "\n";
}
}
|
cs |
17613번: 점프
T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫
www.acmicpc.net
점프
한번 점프를 하면 초항이 1이고 등비가 2인 공비수열처럼 점프를 계속 하게 됩니다.
따라서 특정 수 a에 도달하기 위해 최소로 점프를 하는 방법은 점프를 최대한 초기화 시키지 않고 a에 근접하게 가고, 점프를 초기화, 그리고 거기서 또 a에 가장 근접하게 점프를 계속 하고 점프를 초기화... 이런 방법을 반복해서 가는 것이 가장 적은 점프수로 a에 도달 할 수 있는 방법입니다.
따라서 우리는 전체 수를 [2^n-1, 2^(n+1)-2] 이란 특정 구간들로 모두 나눌 수 있고,
특정 [s, e]구간이 존재한다면, [s, e]사이의 구간 [a, b]가 특정 [2^n-1, 2^(n+1)-2] 구간에 포함된다면,
[a, b]구간에서 최소점프로 갈수 있는 곳에 도달하기 위한 점프수를 J(n)이라 하고
[a- (2^n-1), b - (2^n-1)]구간에서 최소점프로 갈 수 있는 곳에 도달하기 위한 점프수를 J'(n)이라고 한다면
J(n) = J'(n) + n 이라는 점화실을 얻을 수 있습니다.
따라서 구간 [s, e]를 위의 점화식 조건을 사용 할 수 있게 [s, b(0)], [a(1), b(1)], .... , [a(n), e] 로 나누고 점화식을 사용 한다면 각각의 나누어진 구간에서 최소점프로 갈수 있는 곳중 최대의 점프 횟수를 구할 수 있습니다.
이때 [2^n-1, 2^(n+1)-2]과 같은 자주사용되는 특정 구간에 대해 최소점프로 갈수 있는 곳중 최대 점프의 수를 DP로 저장해준다면, 우리는 훨씬 더 빠른 시간안에 문제를 해결 할 수 있습니다.
아니면, [2^n-1, 2^(n+1)-2]의 조건의 최대값은 [0, 2^(n+1)-2]의 조건의 최대값과 같고,
[2^n-1, 2^(n+1)-2]의 최대값은 [0, 2^n-2]의 최대값 + n을 한것과 같습니다 따라서
특정 구간 [2^n-1, 2^(n+1)-2]의 최대값은 1+n*(n+1)/2 라는 식을 얻을 수 있습니다.
