9465 스티커

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int arr[2][110000] = { 0 };
int dp[2][110000] = { 0 };
 
int main() {
    int t,n;
    scanf("%d", &t);
    getchar();
 
    for (int k = 0; k < t; k++) {        
        scanf("%d", &n);
        getchar();
 
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= 2; j++) {
                dp[i][j] = arr[i][j];
            }
        }
        dp[1][2] += dp[2][1];
        dp[2][2] += dp[1][1];
        
        for (int j = 3; j <= n; j++) {
            dp[1][j] = max(dp[2][j - 1], dp[2][j - 2]) + arr[1][j];
            dp[2][j] = max(dp[1][j - 1], dp[1][j - 2]) + arr[2][j];
        }
 
        int result = max(dp[1][n], dp[2][n]);
        printf("%d\n", result);        
    }
}