Monsters And Spells(dp/rmq)

87 阅读 0 评论 58 点赞

我是靠谱客的博主冷艳哈密瓜，这篇文章主要介绍Monsters And Spells(dp/rmq)，现在分享给大家，希望可以做个参考。

题目
题意：有n只怪兽，每只怪兽在 $k_i$ 时间点会出现，且生命值为 $h_i$ 。现在我们需要消灭这 $n$ 只怪兽。由于我们每次打气功，都需要从1开始累计，比如上一秒是打的气功是x，那么这一秒可以打x+1，或者选择重新开始，气功为1。如果上一秒没有打气功，则这一秒只能打1。要消灭这 $n$ 只小怪兽，我们总共需要消耗的最小气功是多少。

思路：
先根据每只小怪兽的生命值，计算消灭这只小怪兽，需要从哪里开始打气功 $pos_i$ ，比如 $k_i=6,h_i=3$ ，说明我们需要在时间点6-3+1=4的位置开始打气功。如果要批量处理连续区间内的小怪兽，我们需要计算区间 $[l, r]$ 的最小打气功的开始位置 $p$ ，然后计算从 $p$ 到 $k_r$ 的气功总和即可。

由于本题的n比较小，可以支持 $n^2$ 的复杂度。我们可以用dp。令 $dp_i$ 表示从i位置结束需要的最小气功。那么 $dp_i = dp_{j-1} + deal(j,i),(0<j<=i)$ 。

计算区间最小值，可以用rmq算法。
注意，如果当前区间 $[j, i]$ 的最小开始下标 $p$ ，小于上一个区间的结束下标位置 $k_{j-1}$ ，则说明区间 $[j, i]$ 的打气功位置和前面的区间发生了交叉，这是不可取的。

复制代码

#include<bits/stdc++.h> 
using namespace std;
const int maxn = 110;
#define ll long long

int n;
ll dp[maxn];
int h[maxn], k[maxn];
int pos[maxn];// 下标i需要的开始位置pos[i]

ll cal(ll x) {
	return x * (x + 1) / 2;
}

// rmq求pos数组区间 最小值 
int f[maxn][22];
void init_rmq() {
	for (int i = 0; i < n; ++i) {
		f[i][0] = pos[i];
	}
	for (int j = 1; (1<<j) <= n; ++j) {
		for (int i = 0; i + (1<<j) - 1 < n; ++i) {
			f[i][j] = min(f[i][j-1], f[i+(1<<j-1)][j-1]);
		}
	}
}
int rmq(int l, int r) {
	int x = log2(r - l + 1);
	return min(f[l][x], f[r-(1<<x)+1][x]);
}

void solve() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &k[i]);
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &h[i]);
	}
	for (int i = 0; i < n; ++i) {
		pos[i] = k[i] - h[i] + 1;
//		printf("%d ", pos[i]);
	}
//	printf("--n");
	
	init_rmq();
	dp[0] = cal(h[0]);
//	printf("%d", dp[0]);
	for (int i = 1; i < n; ++i) {
		int p = k[i] - rmq(0, i) + 1;
		dp[i] = cal(p);
		for (int j = 1; j <= i; ++j) {
			// 起始下标超过了上个区间的结束位置，说明有交叉，不可取
			if (rmq(j, i) <= k[j-1]) { 
				continue;
			}
			p = k[i] - rmq(j, i) + 1;
			
			dp[i] = min(dp[i], dp[j-1] + cal(p));
		}
//		printf(" %d ", dp[i]);
	}
//	printf("---n");
	
	printf("%lldn", dp[n-1]);
}

int main() {
	int t;
	scanf("%d", &t);
//	int cas = 1;
	while (t--) {
//		printf ("case %dn", cas++);
		solve();
	}
} 
/*

9
3
1 2 4
1 2 3

3
1 2 3
1 1 2
*/

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h> 
using namespace std;
const int maxn = 110;
#define ll long long

int n;
ll dp[maxn];
int h[maxn], k[maxn];
int pos[maxn];// 下标i需要的开始位置pos[i] 

ll cal(ll x) {
	return x * (x + 1) / 2;
}

// rmq求pos数组区间 最小值 
int f[maxn][22];
void init_rmq() {
	for (int i = 0; i < n; ++i) {
		f[i][0] = pos[i];
	}
	for (int j = 1; (1<<j) <= n; ++j) {
		for (int i = 0; i + (1<<j) - 1 < n; ++i) {
			f[i][j] = min(f[i][j-1], f[i+(1<<j-1)][j-1]);
		}
	}
}
int rmq(int l, int r) {
	int x = log2(r - l + 1);
	return min(f[l][x], f[r-(1<<x)+1][x]);
}

void solve() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &k[i]);
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &h[i]);
	}
	for (int i = 0; i < n; ++i) {
		pos[i] = k[i] - h[i] + 1;
//		printf("%d ", pos[i]);
	}
//	printf("--n");
	
	init_rmq();
	dp[0] = cal(h[0]);
//	printf("%d", dp[0]);
	for (int i = 1; i < n; ++i) {
		int p = k[i] - rmq(0, i) + 1;
		dp[i] = cal(p);
		for (int j = 1; j <= i; ++j) {
			// 起始下标超过了上个区间的结束位置，说明有交叉，不可取
			if (rmq(j, i) <= k[j-1]) { 
				continue;
			}
			p = k[i] - rmq(j, i) + 1;
			
			dp[i] = min(dp[i], dp[j-1] + cal(p));
		}
//		printf(" %d ", dp[i]);
	}
//	printf("---n");
	
	printf("%lldn", dp[n-1]);
}

int main() {
	int t;
	scanf("%d", &t);
//	int cas = 1;
	while (t--) {
//		printf ("case %dn", cas++);
		solve();
	}
} 
/*

9
3
1 2 4
1 2 3

3
1 2 3
1 1 2
*/