#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <map>
#include <cstring>
// 9465번. 스티커
// 16:29 ~
int dp[100001][3];
int v[100001][2];
int main()
{
// n이 20만임.
// 40만의 탐색 시간이 걸리므로.
// 다른 효율적인 방법을 찾아야 함.
// 총 2가지의 경우의 수가 있음.
// 열의 갯수, 스티커를 어떻게 처리할 것인가?
// 위쪽 스티커 뜯기 , 아래쪽 스티커 뜯기
// 위쪽 뜯으면 0
// 아래 뜯으면 1
// 안뜯으면 2
// 위쪽스티커를 뜯을 경우,
// dp[n][0] = max( dp[n - 1][1] , dp[n - 1][2] ) + v[n][0]
// 아래쪽 스티커 뜯을 경우.
// dp[n][1] = max( dp[n - 1][0] , dp[n - 1][2] ) + v[n][1]
// 스티커를 안 뜯으면?
// 0이 아닐까 생각할 수 있는데...
// 위쪽과 아래쪽에 영향을 주기 위해서, 뭔가 작성을 해야함.
// dp[n][2] = max(dp[n - 1][0] , dp[n - 1][1] , dp[n - 1][2]);
int t, n;
cin >> t;
for (int i = 0; i < t; ++i)
{
cin >> n;
//vector<vector<int>>v(2, vector<int>(n));
for (int j = 0; j < n; j++) {
cin >> v[j][0];
}
for (int j = 0; j < n; j++) {
cin >> v[j][1];
}
memset(dp, -1, sizeof(dp));
dp[0][0] = dp[0][1] = dp[0][2] = 0;
for (int a = 1; a <= n; ++a)
{
dp[a][0] = max(dp[a - 1][1], dp[a - 1][2]) + v[a - 1][0];
dp[a][1] = max(dp[a - 1][0], dp[a - 1][2]) + v[a - 1][1];
dp[a][2] = max({ dp[a - 1][0], dp[a - 1][1], dp[n - 1][2] });
}
cout << max({ dp[n][0], dp[n][1], dp[n][2] }) << "\n";
// max 3개 이상 원소 비교할 때는 {} 중괄호 붙여야 함.
}
}
=> 예제는 맞지만, 틀림으로 나옴...
틀렸지만, 정신을 부여잡고, 점화식을 다시 한번 만들어보는 시도를 해야함.
코딩테스트에서 이럴 경우 어쩔겨!
반례를 찾기에는 0%에서 틀렸으니까 다시 만들어보자.
n번째 열까지 진행하고 + 뜯고, 위쪽 뜯어? 아래쪽 뜯어 총 3번의 경우의 수를 가지므로 점화식은 이렇게 나타낼 수 있음.
dp[i][3] : i번 열에서 스티커를 안뜯어, 위쪽 뜯어, 아래쪽 뜯었을 때의 최대값
0 : 안 뜯어
dp[i][0] : max(dp[i - 1][0] , dp[i -1][1] , dp[i - 1][2]); 이런식으로.
1 : 위쪽 뜯어
dp[i][1] : max(dp[i -1][0] ,dp[i -1][2] ) + 현재 인덱스의 위쪽부분 원소
//=> 이런식으로...