A41778. 上机又到周末了，同学们陆陆续续开开心心的来到机房上机。jbr也不例外，但是他到的有点晚，发现有些机位上已经有同学正在做题，有些机位还空着。细心的jbr发现，一位同学来到机房，坐在机位i上，如果他的左右两边都空着，他将获得能力值a[i]；如果当他坐下时，左边或者右边已经有一个人在上机了，他将获得能力值b[i]；如果当他坐下时，他的左边右边都有人在上机，他将获得能力值c[i]。同时他发现，已经在上机…
题目描述
上机
又到周末了，同学们陆陆续续开开心心的来到机房上机。jbr也不例外，但是他到的有点晚，发现有些机位上已经有同学正在做题，有些机位还空着。细心的jbr发现，一位同学来到机房，坐在机位i上，如果他的左右两边都空着，他将获得能力值a[i]；如果当他坐下时，左边或者右边已经有一个人在上机了，他将获得能力值b[i]；如果当他坐下时，他的左边右边都有人在上机，他将获得能力值c[i]。
同时他发现，已经在上机的同学不会受到刚要坐下的同学的影响，即他们的能力值只会在坐下时产生，以后不会发生变化;第一个机位左边没有机位，最后一个机位右边没有机位，无论何时坐在这两个机位上将无法获得c值。
这时jbr发现有一排机器还空着，一共有N个机位，编号1到N。这时有N位同学们陆陆续续来到机房，一个一个按照顺序坐在这排机位上。聪明的jbr想知道怎么安排座位的顺序，可以使这N位同学获得能力值的和最大呢？
输入
第一行一个整数N(1<= N <= 10000)
第二行N个数，表示a[i]
第三行N个数，表示b[i]
第四行N个数，表示c[i]
(1<= a[i],b[i],c[i] <=10000)
输出
一个整数，表示获得最大的能力值和
样例输入
4
1 2 2 4
4 3 3 1
2 1 1 2
样例输出
14
提示
第一位同学坐在第四个机位上，获得能力值4； 第二位同学坐在第三个机位上，获得能力值3； 第三位同学坐在第二个机位上，获得能力值3； 第四位同学坐在第一个机位上，获得能力值4； 总和为14。
/*示例代码 dp
dp[i][0]定义为 i-1, i, i+1中, i第一个到
dp[i][1]定义为i-1, i, i+1中, i-1第一个到且i第二个到
dp[i][2]定义为i-1, i, i+1中, i+1第一个到且i第二个到
dp[i][3]定义为 i-1, i, i+1中, i第三个到
*/
参考答案
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000 +1;
int a[N], b[N], c[N], dp[N][4];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
//初始化第一个机位
dp[1][0] = a[1];//1可以最早到
dp[1][1] = -INF;//1无左邻居 无
dp[1][2] = b[1];//1右邻居最早到
dp[1][3] = -INF;//1无左邻居 无
for (int i = 2; i <= n; i++) {
dp[i][0] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);//i第一个到：i-1就需要第二个到或第三个到
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][1]);//i-1第一个到且i第二个到：i-1就需要第一个到
dp[i][2] = b[i] + max(dp[i - 1][2], dp[i - 1][3]);//i+1第一个到且i第二个到：i-1就需要第三个到
dp[i][3] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);//i第三个到: i-1就需要早于i到
}
printf("%d\n", max(dp[n][0], dp[n][1]));//最后一个机位无右邻居
return 0;
}