題目描述

小明建造了一個籃球場，他請來了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;
}