[기출] 산책하자

[문제]

- N: 마을의 수 (2 ≤ N ≤ 100,000)
- Ai: 이웃한 마을간 산책로의 수 (1 ≤ Ai ≤ 1,000,000,000 십억)
- 산책을 출발하면 이웃한 마을로만 이동이 가능하며, 한번 지난 산책로는 다시 지나지 않는다.
- 어떤 마을에서든 산책을 시작할 수 있고, 어떤 마을에서든 마칠 수 있다.

 

[알고리즘]

DP

 

[Key Point]

- 임의의 마을(Ai) 은 아래 세 가지 경우를 포함한다.

  . L[Back] + R[Back] : 좌우를 모두 다녀오는 경우

  . L[Go] + R[Back] : 우측을 돌고 좌측으로 가는 경우

  . L[Back] + R[Go] : 좌측을 돌과 우측으로 가는 경우

- 점화식:

  L[i][Back] = L[i-1][Back] + 짝수(r[i-1]) 

  R[i][Back] = R[i+1][Back] + 짝수(r[i]) 

  L[i][Go] = max(L[i-1][Back], L[i-1][Go]) + 홀수(r[i-1]) 

  R[i][Go] = max(R[i+1][Back], R[i+1][Go]) + 홀수(r[i])

 

[구현코드]

// test-p0081.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// 유사문제: 팀구성

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100002;
enum { GO = 0, BACK};

int T, N;
int r[MAX_N];
long long L[MAX_N][2];
long long R[MAX_N][2];
int c[2];
long long ans[MAX_N];

void GetRoadCount(const long long roads)
{
	if (roads == 1) {
		c[GO] = 1;
		c[BACK] = 0;
	}
	else if (roads % 2 == 0) {
		c[GO] = roads - 1;
		c[BACK] = roads;
	}
	else {
		c[GO] = roads;
		c[BACK] = roads - 1;
	}
}

int main()
{
	setbuf(stdout, NULL);
#ifdef _DEBUG
	freopen("input2.txt", "r", stdin);
#endif
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d", &N);

		memset(&r, NULL, sizeof(r));
		memset(&L, NULL, sizeof(L));
		memset(&R, NULL, sizeof(R));
		memset(&ans, NULL, sizeof(ans));

		for (int i = 1; i < N; i++) {
			scanf("%d", &r[i]);
		}

		for (int i = 2; i <= N; i++) {
			GetRoadCount(r[i - 1]);
			L[i][GO] = max(L[i - 1][GO], L[i - 1][BACK]) + c[GO];
			L[i][BACK] = L[i - 1][BACK] + c[BACK];
			if (r[i - 1] == 1) {
				L[i][BACK] = 0;
			}
		}

		for (int i = N-1; i >= 1; i--) {
			GetRoadCount(r[i]);
			R[i][GO] = max(R[i + 1][GO], R[i + 1][BACK]) + c[GO];
			R[i][BACK] = R[i + 1][BACK] + c[BACK];
			if (r[i] == 1) {
				R[i][BACK] = 0;
			}
		}

		ans[1] = max(R[1][GO], R[1][BACK]);
		ans[N] = max(L[1][GO], L[1][BACK]);
		
		long long answer = max(ans[1], ans[N]);
		for (int i = 2; i < N; i++) {
			ans[i] = max(L[i][BACK] + R[i][BACK], max(L[i][BACK] + R[i][GO], L[i][GO] + R[i][BACK]));
			answer = max(answer, ans[i]);
		}

		printf("#%d %lld\n", tc, answer);
	}
}

(입력)

5
5
3 1 2 1
5
4 1 1 2
3
2 2
7
1 2 3 4 5 6
13
1 1 1 1 1 1 1 1 1 1 1 1

 

(출력)

#1 6
#2 8
#3 4
#4 19
#5 12