BOJ 9465. 스티커

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

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	/* 
	dp[i][j] : (i, j) 위치일 떄의 최댓값
	dp[n][0] = MAX{ dp[n-1][1], dp[n-2][0], dp[n-2][1] }
	dp[n][1] = MAX{ dp[n-1][0], dp[n-2][0], dp[n-2][1] }
	*/
	static int[][] input, dp;

	static int go(int r, int c) {
		if (r == 1) {
			dp[r][c] = input[r][c];
			return dp[r][c];
		} 
		else if (r < 1) return 0;

		if (dp[r][c] != -1) return dp[r][c];

		dp[r][c] = 0;
		dp[r][c] = Math.max(dp[r][c], go(r-1, 1-c));
		dp[r][c] = Math.max(dp[r][c], go(r-2, c));
		dp[r][c] = Math.max(dp[r][c], go(r-2, 1-c));

		dp[r][c] += input[r][c];

		return dp[r][c];
	}
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int testcase = Integer.parseInt(in.readLine());
		for (int tc = 0; tc < testcase; tc++) {
			N = Integer.parseInt(in.readLine());
			input = new int[N + 1][2];
			dp = new int[N + 1][2];
			for (int[] d : dp) Arrays.fill(d, -1);
			for (int i = 0; i < 2; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				for (int j = 1; j <= N; j++)
					input[j][i] = Integer.parseInt(st.nextToken());
			}
			System.out.println(Math.max(go(N, 0), go(N, 1)));
		}
	}
}