水果游戏

水果游戏"/>

水果游戏

哲秀找到了一个新的游戏。游戏是在横向 W格，竖向H格大小的2维格子上进行。

各格子是用坐标表示。最左下方格子用(1, 1)，最右上方的格子用(W, H)表示。

哲秀的character可在格子最低下行的任意格子上开始。即，哲秀可以选择开始的格子位置。

哲秀的character可以在当前格子上，只能以向上，45度方向的左上方，45度方向的右上方的3种方向移动到相邻的格子，每次移动一次，且反复执行如上所述的移动。

格子上会有一个水果，当哲秀到达有水果的格子时，会吃到水果。每次吃水果时的满足度有所不同。

当哲秀按照如上一样移动吃水果时，请编写求出可获得的最大满足度之和的程序。

如下案例一样，根据虚线表示的方法移动的话，可以吃到最多个数的水果，但满足度之和不是最高。获得满足度之和最高的方法是按照图片中实线表示的方法进行移动。

[输入]

Input的第一行给出包含的测试用例个数T。

每个测试用例的第一行给出格子的横向大小W，竖向大小 H，水果的个数N。(1 ≤ W ≤ 50, 1 ≤ H ≤ 109 , 1 ≤ N ≤ 200,000)

然后通过N行，每行按照顺序给出各水果位置的横向坐标，竖向坐标，满足度。

横向坐标是1以上W以下，竖向坐标是1以上H以下，满足度是1以上109 以下。水果的位置不会重叠。

[输出]

对各测试用例的答案，每个测试用例输出一行。首先输出#x(x是测试用例号码，从 1开始)，隔一个空格后，输出可以获得的最大满足度之和。

[输入输出 案例]

(输入)

2

4 5 4

4 4 2

4 5 5

1 1 3

2 5 8

2 3 3

1 1 2

2 2 3

1 3 4

(输出)

#1 11

#2 9

package sw.pro;import java.io.*;
import java.util.*;class Main {static int T, W, H, N, off;static Long[] top = new Long[128];static Long[] bottom = new Long[128];static Long ans;static Map<Integer, TreeMap<Integer, Long>> MAP = new TreeMap<>();public static void main(String args[]) throws Exception {//long start = System.currentTimeMillis();//System.setIn(Solution.class.getResourceAsStream("input.txt"));BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String line;StringTokenizer st;T= Integer.parseInt(br.readLine());for (int t = 1; t <= T; t++) {line = br.readLine();st = new StringTokenizer(line);W = Integer.parseInt(st.nextToken());H = Integer.parseInt(st.nextToken());N = Integer.parseInt(st.nextToken());MAP.clear();ans = 0L;for (int i = 0; i < N; i++) {line = br.readLine();st = new StringTokenizer(line);Integer w = Integer.valueOf(st.nextToken());Integer h = Integer.valueOf(st.nextToken());Long s = Long.valueOf(st.nextToken());if (!MAP.containsKey(h))MAP.put(h, new TreeMap<Integer, Long>());MAP.get(h).put(w, s);}mm();System.out.printf("#%d %d\n", t, ans);}//System.out.printf("Time: %d\n", System.currentTimeMillis() - start);}static void mm(){Long[] swap;Arrays.fill(top, 0L);Arrays.fill(bottom, 0L);Integer pre = 0;off = 1;while (off < W) off <<= 1;for (Map.Entry<Integer, TreeMap<Integer, Long>> entry : MAP.entrySet()) {Integer i = entry.getKey();Integer dh = i - pre;Long max;TreeMap<Integer, Long> row = entry.getValue();for (Integer j = 1; j < W+1; j++) {Long val = row.get(j);if (val == null)val = 0L;if (dh >= W - 1)max = bottom[1];elsemax = getMax(off+j-1-dh, off+j-1+dh);top[off + j - 1] = val + max;}for (int j = off -1; j > 0; j--)top[j] = Math.max(top[j<<1], top[(j<<1)+1]);pre = i;swap = bottom;bottom = top;top = swap;}ans = bottom[1];}static Long getMax(int start, int end){Long max = 0L;if (start < off) start = off;if (end > off+W-1) end = off+W-1;while (start <= end){if ((start & 1) == 1){max = Math.max(bottom[start], max);}if ((end & 1) == 0){max = Math.max(bottom[end], max);}start = (start+1) >> 1;end = (end-1) >> 1;}return max;}
}