Codeforces Round#574(Div.2)——C.Basketball Exercise(単純DP)

テーマゲート

大体の問題：

nを入力して、2つのグループがいずれもn個の数字の配列aとbを与えて、順番にaとbの配列の中から1つの数字を取り出して、厳格に現在の選択した数字の配列の下のスケールに従って前の選択した数字の配列の下のスケールよりもっと大きくて、取り出すことができる数字の合計の最大エネルギーを計算します.テストサンプル1:
入力:5 9 3 5 7 3 5 8 1 4 5
出力:29
ヒント:下に線を引いた数字(9 8 5 4 3)9 3 5 7 3 8 4 5を選択します.
テストサンプル2:
入力:3 1 2 9 10 1
出力:19
ヒント:(選択10 9)1 2 9 10 1

問題:

簡単なdp問題は,選択と非選択の2つの状態を考慮し,dp配列0が先取aの場合,1が先取bの場合である.

#include
typedef long long ll;
using namespace std;
ll n,a[100005],b[100005],dp[2][100005];
int main()
{
    ios::sync_with_stdio(false);
    while(!(cin>>n).eof()){
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        for(int i=1;i<=n;i++){
            dp[1][i]=max(dp[0][i-1]+b[i],dp[1][i-1]);
            dp[0][i]=max(dp[1][i-1]+a[i],dp[0][i-1]);
        }
        cout<<max(dp[1][n],dp[0][n])<<endl;
    }
    return 0;
}