[백준 9465] 스티커

요구사항

스티커의 조건이 주어졌을때, 스티커의 합 최대로 구하기

 

풀이

n이 100,000이니깐 완전 탐색으로는 힘들다

스티커를 고르는 조건은 2개이다

현재 자리 고르고 다음 칸의 반대편 층 수 고르기

and

현재 자리 고르고 다다음 칸의 같은 층 수 고르기

 

n-1칸의 1층, 2층 중 최대값이 dp배열에 저장된다

 

#pragma warning(disable:4996)
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;
int d[2][100100];
int map[2][100100];
int n;
int func(int floor, int pos) {
	if (pos < 0) return 0;
	if (pos == 0) {
		if (floor == 1) return map[floor][pos];
		else return map[floor][pos];
	}

	int &ref = d[floor][pos];
	if (ref != -1) return d[floor][pos];

	if (floor == 0) ref = map[floor][pos] + max(func(1, pos - 1), func(1, pos - 2));
	else ref = map[floor][pos] + max(func(0, pos - 1), func(0, pos - 2));
	return ref;
	
}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		int n;
		scanf("%d", &n);
		memset(d, -1, sizeof(d));
		for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) scanf("%d", &map[i][j]);
		int ans = max(func(1, n - 1), func(0, n - 1));
		cout << ans << endl;

	}
}