[백준/C++] Stickers

Stickers

Nancy, your little sister, has a sheet of 2n stickers of rectangular shape that are arranged in 2 rows and n columns. See Figure 1(a). Nancy wants to decorate her desk with the stickers. But the quality of the stickers is poor, and tearing off one sticker from the sheet spoils the stickers sharing an edge with it. So, Nancy must lose the stickers above, below, to the left of, and to the right of the sticker she tears off.

Figure 1. A sheet of 10 stickers in 2 rows

Nancy had no idea about what to do. You looked at her and suggested that she should score each sticker and try to choose a possible set of stickers that maximizes the total score. Nancy marked scores to all the 2n stickers as in Figure 1(b). And Nancy had no idea, again. You again took a look at her and sighed. You cannot help doing something for her, and at last decided to help her with a fast computer program. Your program is to select a set of stickers of maximum total score from the 2n stickers such that no two of them share an edge.

In the example shown in Figure 1, the maximum total score is 260 when you select the four stickers of scores 50, 50, 100, 60. Unfortunately, in this case, it is not allowed to simultaneously select both of the two highest scored stickers (of score 100 and 70) because the two stickers share an edge between them.

입력 Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line that contains an integer (1 ≤ n ≤ 100,000), where 2n is the number of stickers in the sheet. In the next two lines, each line contains n integers, each of which represents Nancy’s score for the sticker at that position in the sticker sheet. Every two consecutive integers in a line are separated by a blank. Note that the 2n stickers are of rectangular shape and are arranged in 2 rows and n columns in the sheet. Nancy’s scores range from 0 to 100.

출력 Your program is to write to standard output. Print exactly one line for each test case. The line should contain the maximum possible total score for a subset of the 2n stickers such that no two stickers share an edge.

예제 입력 1

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력 1

260
290

풀이

동물원문제와 상당히 닮아있다. 아니, 똑같다고 본다. 여기서도, 특정 열을 선택하지 않는 것이 더 큰 비용이 나오도록 만들 수 있으므로 고르지 않는 경우도 하나의 경우로 쳐야 한다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int D[3][100001], arr[3][100001];

int DP(int L, int i)
{
	if (D[L][i] != -1)
		return D[L][i];
	if (L == 0)
		return D[L][i] = max({DP(0, i - 1), DP(1, i - 1), DP(2, i - 1)});
	if (L == 1)
		return D[L][i] = max(DP(0, i - 1) + arr[L][i], DP(2, i - 1) + arr[L][i]);
	if (L == 2)
		return D[L][i] = max(DP(0, i - 1) + arr[L][i], DP(1, i - 1) + arr[L][i]);
}

int main()
{
	int T, n;
	cin >> T;
	while(T--) {
		memset(arr, 0, sizeof(arr));

		cin >> n;
		for(int i = 1; i <= 2; ++i)
			for(int j = 1; j <= n; ++j)
				cin >> arr[i][j];

		memset(D, -1, sizeof(D));
		D[0][1] = 0; D[1][1] = arr[1][1]; D[2][1] = arr[2][1];

		cout << max({DP(0, n), DP(1, n), DP(2, n)}) << "\n";
	}
	return 0;
}

끝