#include <stdio.h>
int dp[2][100001];
int num[2][100001];
int max(int a,int b) {
    return a>b ? a:b;
}
int bottom_up(int n) {
    //기저
    dp[0][0]=num[0][0];
    dp[1][0]=num[1][0];
    dp[0][1]=dp[1][0]+num[0][1];
    dp[1][1]=dp[0][0]+num[1][1];
    for(int i=2; i<n; i++) {
        dp[0][i]=max(dp[1][i-1],dp[1][i-2])+num[0][i];
        dp[1][i]=max(dp[0][i-1],dp[0][i-2])+num[1][i];
    }
    return max(dp[0][n-1],dp[1][n-1]);
}


int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        int n;
        scanf("%d",&n);
        for(int i=0; i<2; i++){
            for(int j=0; j<n; j++) {
                scanf("%d", &num[i][j]);
            }
        }
        printf("%d\n",bottom_up(n));
    }
    return 0;
}

Embed on website

To embed this project on your website, copy the following code and paste it into your website's HTML: