链接：

https://codeforces.com/problemset/problem/1195/C

题意：

两个数列a和b，每次可以在任意一个数字中取一个数字（可以不取）求和值最大

解：

DP冲冲冲！

dp二维数组dp【 i 】【 j 】

i表示第 i 天 j 选择的最优选择

j=0不选，j=1选a数列，j=2选b数列

DP转移公式

dp[i] [0]=max(dp[i-1] [0],max(dp[i-1] [1],dp[i-1] [2]));
dp[i] [1]=max(dp[i-1] [0]+sz[i] [0],dp[i-1] [2]+sz[i] [0]);
dp[i] [2]=max(dp[i-1] [0]+sz[i] [1],dp[i-1] [1]+sz[i] [1]);

实际代码：

#include<iostream>
#include<bits/stdc++.h>
#define csh(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long int ll;
const int Size=2E5+10;
int sz[Size][2];
ll dp[Size][3];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>sz[i][0];
	for(int i=1;i<=n;i++) cin>>sz[i][1];
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
		dp[i][1]=max(dp[i-1][0]+sz[i][0],dp[i-1][2]+sz[i][0]);
		dp[i][2]=max(dp[i-1][0]+sz[i][1],dp[i-1][1]+sz[i][1]);
	}
	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;
}

限制：

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output