【dp树状数组优化】跳跃（jump)

题目：

题目

猴子的正上方，每1米处，都有一个桃子，一共有N个桃子，每个桃子都有其能量值，摘下这个桃子吃下就获得了这个能力值。猴子每跳1米会消耗1个点能量，在能量值允许的下，它可以跳到任何一个可以到达的高度，并且将这个高度及以下高度的桃子摘下吃掉。确保猴子初始的能量一定可以摘下所有的桃子。求该猴子摘下吃掉所有的桃子后，保留最多的能量值

输入格式

第一行  两个整数N和M,表示桃子的数量和猴子的初始能量

第二行，N个非负整数，依次描述从下向上描述各桃子的能量值。
输出格式

一个整数，意义如题所述。
输入输出样列
输入样例：

3 2
2 2 2


输出样例：

4

数据范围

1 <= N <= 2000000
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

思路1 dfs（20分）：
dfs爆搜每一种情况，但是会TLE。
思路2 dp（70分）：
定义状态：d[i]表示摘前i个桃子可以保留的最大能量值，最终答案为d[n];
状态转移：考虑第i个桃子：
①i单独一次摘：d[i] = d[i-1] - i + a[i];
②i和i-1一起摘：d[i] = d[i-2] - i + a[i] + a[i-1];
③[i-2, i]一起摘：d[i] = d[i-3] - i + sum(i-2, i);
…
i: [1, i]一起摘：d[i] = d[0] - i + sum(1, i);
d[i] = max(d[j] + sum[j+1, i])- i ; //(0 <= j <= i-1 && d[j] - i >= 0);
核心代码：

for (int i = 1; i <= n; i++) {
	int mx = 0 ;
	for (int j = 0; j < i; j++)
		mx = max (mx , dp[j] + sum[i] - sum[j]) ;
	dp[i] = mx - i ;
}
1
2
3
4
5
6

依然会TLE，但是到了70分了，说明我们的思路是对的，可以试试进一步优化。
思路3 树状数组优化（100分）：
这道题是求一个dp[i]的题，dp[i] = dp[j] - sum[j]的最大值 + sum[i] - i ;
其实他就是一个前缀问题，因为j是在一个前缀范围（0 ~ i - 1)
所以我们可以通过树状数组优化时间复杂度到：O(nlog2n)
注意开long long。
代码：

#include 
#pragma GCC optimize(2)

using namespace std ;

typedef long long LL ;
const int N = 2000010 ;
LL n , sum[N] , dp[N] , m , C[N] ;
void update (LL x , LL y) {
	while (x) {
		C[x] = max (C[x] , y) ;
		x -= (x & - x) ;
	}
}
LL query (LL x) {
	LL res = -9223372036854775807 ;
	while (x <= n && x) {
		res = max (res , C[x]) ;
		x += (x & - x) ;
	}
	return res ;
}

int main ()
{


    for (int i = 1; i <= 2000000; i++)
        C[i] = -9223372036854775807 ;
	scanf ("%lld%lld" , & n , & m) ;
	for (int i = 1; i <= n; i++)
		scanf ("%lld" , & sum[i]) , sum[i] += sum[i - 1] ;
	dp[0] = m ;
	update (m , m) ;
	LL j = 0 , mx = -9223372036854775807 ;
	for (int i = 1; i <= n; i++) {
		LL p = query (i) ;
		dp[i] = p + sum[i] - i ;
		if (dp[i] <= n && dp[i] >= 0)
			update (dp[i] , dp[i] - sum[i]) ;
		else
			mx = max (mx , dp[i] - n + sum[n] - sum[i]) ;
	}
	printf ("%lld" , max (dp[n] , mx)) ;



	return 0 ;
}
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