简单递归

首先我们如果要消灭一段区间$[l, r]$,我们可以有三种选择:

  • 如果$[l, r]​$区间内没人,那么直接花费$A​$的代价将这段摧毁
  • 如果$r > l​$(即这段区间长度$>2​$),可以选择把它切割成$\left[ l, \lfloor \frac{l + r}2\rfloor\right]​$ $\left[\lceil \frac{l + r}2\rceil, r\right]​$两段
  • 如果$[l, r]$区间内有人,直接花费$b (r - l + 1)x$的代价将其摧毁。

那么我们可以直接递归寻找对于每个区间的最优解

但是如果暴力找,那么是$O(2^n)​$的。

然后我们可以发现一个很显然的结论,就是若一个区间内没人,那么第一种方案是肯定最优的。

可以理解成动态开点线段树上的$DP​$

将这个优化加上去之后复杂度就是正确的QwQ

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<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define int long long

int inp(){
char c = getchar();
int neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
neg = -1;
c = getchar();
}
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return neg * sum;
}

int pos[100010];
int n, k, a, b;

int solve(int l, int r){
int cnt = std::upper_bound(pos + 1, pos + k + 1, r) - std::lower_bound(pos + 1, pos + k + 1, l);
// printf("cnt [%d, %d] = %d\n", l, r, cnt);
int mid = (l + r) >> 1;
if(l == r && cnt != 0)
return (r - l + 1) * cnt * b;
return (cnt == 0) ? a : std::min((r - l + 1) * cnt * b, solve(l, mid) + solve(mid + 1, r));
}

signed main(){
n = inp();
k = inp();
a = inp();
b = inp();
for(int i = 1; i <= k; i++)
pos[i] = inp();
std::sort(pos + 1, pos + k + 1);
printf("%I64d\n", solve(1, 1 << n));
return 0;
}

 评论