垫脚石

（测试用例总数：40 个，1.5 秒 (C/C++)，2 秒 (JAVA)/内存要求：256 M，堆栈 1 M）

Lia 在一个景点看到了由 N 个垫脚石组成的石桥。单纯地走过这些垫脚石感觉没有意思，所以她给每块垫脚石设置了一个分数，将踩到的所有石头上的分数全部加起来，想要得到一个最大分数。

但是，为了让这件事更有意思，她决定按下列规则来过桥。

1.第一块和最后一块垫脚石必须要踩。

2.设定一个K值，下一块踩的石头与上一块踩的石头间相隔的距离最大为 K。

3.不能重复踩同一块垫脚石。

 

[图]

假设 N 是 7，每个石头的分数如上图所示。如果 K 是 2，按 ① → ② → ④ → ⑥ → ⑦ 的方式移动可以获得最高分数，分数是 1 (-6 + -4 + 4 + -2 + 9)。如果 K 是 3，按 ① → ④ → ⑦ 的方式移动可以获得最高分数，分数是 7 (-6 + 4 + 9)。

请帮助 Lia 计算出按规则踩着垫脚石过桥时，可以获得的最高分数。

 

[限制条件]

1.组成桥的垫脚石数量 N 为介于 1 到 300,000 之间的整数。

2.每个垫脚石的分数在带符号的 32 位整数值范围内。

3.K 为介于 1 到 N 之间的整数。

 

[输入]

首先，给定测试用例数量 T，后面接着输入 T 种测试用例。在每个测试用例的第一行，给定垫脚石数量 N 和距离 K，以空格分隔。在下一行，给定从 1 到 N 号垫脚石每个的分数，以空格分隔。

 

[输出]

每行输出一个测试用例。首先，输出“#x”（其中 x 表示测试用例编号，从 1 开始）加上一个空格，然后输出问题中要求的值。

 

[输入和输出示例]

(输入)

3
7 2
-6 -4 -6 4 -4 -2 9
7 3
-6 -4 -6 4 -4 -2 9
10 2
-3 -4 -2 -1 -7 -5 -9 -4 -7 -5

 

(输出)

#1 1
#2 7
#3 -20

 

思路分析：
从第二个元素开始，求前K个元素的最大值+当前值，求最大值时，并非从原数组中求，而且从得到的最大值数组中求
基本思想是每步都计算最优解，当前元素的最优解是从前K个元素的最优解中得来
求当前元素之前K个元素的最大值，可用Indexed Tree计算

 

package tree;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 从第二个元素开始，求前K个元素的最大值+当前值，求最大值时，并非从原数组中求，而且从得到的最大值数组中求
 * 基本思想是每步都计算最优解，当前元素的最优解是从前K个元素的最优解中得来
 * 求当前元素之前K个元素的最大值，可用Indexed Tree计算
 * @author XA-GDD
 *
 */
public class EQ_SteppingStones_0827 {
	static int T,N,K;
	static int _Max_N = 300000;
	static int [] srcArr = new int[_Max_N];
	static long [] idxTree = new long[_Max_N*4];
	static int offset;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("D:\\workspace\\sw_pro\\test_case\\sample_input_0827.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
	    for(int testCase = 1; testCase<= T;testCase++) {
	    	Arrays.fill(srcArr, 0);
	    	Arrays.fill(idxTree, Long.MIN_VALUE);
	    	
	    	st = new StringTokenizer(br.readLine());
	    	N = Integer.parseInt(st.nextToken());
	    	K = Integer.parseInt(st.nextToken());
	    	
	    	st = new StringTokenizer(br.readLine());
	    	for(int i=0;i<N;i++) {
	    		srcArr[i]=Integer.parseInt(st.nextToken());
	    	}
	    	
	    	
	    	int k=0;
	    	while((1<<k)<N) {
	    		k++;
	    	}
	    	offset = 1<<k;
	    	
	    	
	    	for(int i=0;i<N;i++) {
	    		update(offset+i,srcArr[i]);
	    	}
	    	
	    	for(int i=1;i<N;i++) {
	    		long val = getMaxBefK(i);
	    		update(offset+i,val+srcArr[i]);
	    	}
	    	System.out.printf("#%d %d\n",testCase,idxTree[offset+N-1]);
	    }

	}
	
	static long getMaxBefK(int idx) {		
		int s = idx-K>0?offset+idx-K:offset;
		int e = idx-1>0?offset+idx-1:offset;
		return query(s,e);
	}
	
	static void update(int index,long val) {
		idxTree[index]=val;
		index=index>>1;
	    while(index>0) {
	    	idxTree[index] = Math.max(idxTree[index*2], idxTree[index*2+1]);
	    	index=index>>1;
	    }
	}
	
	static long query(int s, int e) {
		long res=Long.MIN_VALUE;
		while(s<=e) {
			if(s%2==1) {
				res = Math.max(res, idxTree[s]);
			}
			if(e%2==0) {
				res = Math.max(res, idxTree[e]);
			}
			s = (s+1)>>1;
			e = (e-1)>>1;
		}
		return res;
	}

}