ACM_JLINE.

搜索（剪枝）

DFS
字数统计: 551阅读时长: 2 min
2019/03/12 Share

DFS + 剪枝

原题链接：传送门

CF C题

题目大意：

有 2n 个基地，其中 k 个基地是有复仇者的，问把 1 - 2n 个基地都摧毁需要最小的代价。
摧毁一段区间的地基可以选择直接摧毁，代价是 A * na * l , A 题目会直接告诉你， na 区间内存在复仇者的数量，l 是区间长度；或者你也可以把这个大区间平均分成两半， 仍然按之前的方法计算， 然后如果小区间不存在复仇者， 那么摧毁这段的代价直接为 B。

数据范围 :

n (1 ≤ n ≤ 30)
k (1 ≤ k ≤ 105)
A, B ( 1 ≤ A, B ≤ 104)

题解：

这个模型是不是很像线段树，可是 2n 太大了。
如果先不考虑其他操作的代价， 把所有的小区间汇聚在一起时间复杂度 O(2n log(2n))。
这样显然不行， 数据范围中给的 k 才 105，所以很明显是和 k 有关。因为不难发现其实很多区间根本不需要计算代价， 因为很多区间不存在复仇者。
所以 DFS + 剪枝 时间复杂度为 O(k log(k))。
每一段区间的人数也不能前缀和计算， 因为 2n 太大了。 所以可以二分区间查找有多少复仇者。 总是时间复杂度还得加上二分的开销。

Code block

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;

int n, k, A, B, num, x;
int a[100005];

int sum(int l, int r){ //查询 [l, r] 中有几个复仇者
	int L = lower_bound(a, a + num, l) - a;
	int R = upper_bound(a, a + num, r) - a; 
	R--;
	//cout << L << "  " << R << endl;
	return R - L + 1;
}


ll dfs(int l, int r){
	if(sum(l, r) == 0) {
		return A;
	}
	
	ll tmp = (ll)B * (r - l + 1) * sum(l,r);
	if(l == r) return tmp;
	
	ll L = dfs(l, (l + r)/2);
	
	ll R = dfs((l + r)/2 + 1, r);
	
	if(L + R < tmp) tmp = L + R;
	return tmp;  
}
int main(){
	scanf("%d%d%d%d", &n, &k, &A, &B);
	
	for(int i = 0; i < k; i++){
		scanf("%d", &x);
		a[num++] = x;
	}
	
	sort(a, a+num);
	
	printf("%lld\n", dfs(1, (1 << n)));
	return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/03/12/每日一练3_12/

发表日期：March 12th 2019, 8:05:49 pm

更新日期：March 12th 2019, 8:05:39 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. DFS + 剪枝
    1. 1.1. 原题链接：传送门
      1. 1.1.1. 题目大意：
    2. 1.2. 数据范围 :
      1. 1.2.1. 题解：
      2. 1.2.2. Code block
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路