题目描述

小明建造了一个篮球场，他请来了2行n列的人，想让他们进行比赛。每一个人都有一个能力值，第一行分别为h11，h12，…，h1n，第二行为h21，h22，…，h2n。现在小明可以选一些人组成一个最强团队。但是选人是有规则的，因为选一个人会让附近的人都很妒忌，所以他既不会同一行里连续选择2个人，也不会同一列里的连续选择2个人。
现在他希望所选团队的能力值的之和最大，但人太多了，所以他想请聪明的你帮他解决这个问题。解决在满足规则的情况下能力值的和最大为多少？

输入

第一行输入一个整数n（1≤n≤），表示每行中的学生人数。
第二行输入n个整数h[1,1]，h[1,2]，…，h[1，n]（1≤h[1，i]≤），其中h[1，i]表示第一行中的第i个学生能力值。
第三行输入n个整数h[2,1]，h[2,2]，…，h[2，n]（1≤h[2，i]≤），其中h[2，i]表示第二行中的第i个学生能力值。

输出

输出一个整数，表示所选团队中能力值之和最大。 

样例输入

【样例1】
5 
9 3 5 7 3 
5 8 1 4 5
【样例2】
3 
1 2 9 
10 1 1
【样例3】
1 
7 
4 

样例输出

【样例1】
29
【样例2】
19
【样例3】
7

提示

样例1说明：小明可以选择以下团队：9，8，7，5. 
样例2说明：小明可以选择以下团队 

思路分析

动态规划

每一列都有三种选择。dp[j][i]表示在第j列做出第i种选择后的能力值和。

()

option1：不选任何一个学生。

option2：选择能力值为h1的学生。

option3：选择能力值为h2的学生。

对于第0列（0-based indexing），dp[0][0]=0，dp[0][1]=h1[0]，dp[0][2]=h2[0]。

对于第j列(j>0)，dp[j][0]为dp[j-1][0],dp[j-1][1],dp[j-1][2]三数之中最大的值，
dp[j][1]=h1[j]+max(dp[j-1][2],dp[j-1][0])，
dp[j][2]=h2[j]+max(dp[j-1][1],dp[j-1][0])。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<int>h1(n),h2(n);for(int i=0;i<n;i++){cin>>h1[i];}for(int i=0;i<n;i++){cin>>h2[i];}vector<vector<ll>>dp(n,vector<ll>(3,0));dp[0][0]=0;dp[0][1]=h1[0];dp[0][2]=h2[0];for(int i=1;i<n;i++){ll a=dp[i-1][0],b=dp[i-1][1],c=dp[i-1][2],ans;ans=max(a,b);ans=max(ans,c);dp[i][0]=ans;dp[i][1]=h1[i]+max(dp[i-1][2],dp[i-1][0]);dp[i][2]=h2[i]+max(dp[i-1][1],dp[i-1][0]);}ll res;res=max(dp[n-1][0],dp[n-1][1]);res=max(res,dp[n-1][2]);cout<<res;return 0;
}