UVALive 6510 Stickers

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100010;
 4 int dp[maxn][3],a[2][maxn],n;
 5 int main(){
 6     int kase;
 7     scanf("%d",&kase);
 8     while(kase--){
 9         scanf("%d",&n);
10         for(int i = 1; i <= n; ++i)
11             scanf("%d",&a[0][i]);
12         for(int i = 1; i <= n; ++i)
13             scanf("%d",&a[1][i]);
14         memset(dp,0,sizeof dp);
15         for(int i = 1; i <= n; ++i){
16             dp[i][0] = max(dp[i-1][2],max(dp[i-1][0],dp[i-1][1]));
17             dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + a[0][i];
18             dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + a[1][i];
19         }
20         printf("%d\n",max(max(dp[n][0],dp[n][1]),dp[n][2]));
21     }
22     return 0;
23 }
24 /*
25 2
26 5
27 50 10 100 20 40
28 30 50 70 10 60
29 7
30 10 30 10 50 100 20 40
31 20 40 30 50 60 20 80
32 */