描述

又到周末了，同学们陆陆续续开开心心的来到机房上机。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

/* version 1: 记f[0][i]为前i个机器在第i+1台机器后于第i台机器坐人的情况下能力值和的最大值f[1][i]为前i个机器在第i+1台机器先于第i台机器坐人的情况下能力值和的最大值显然我们有f[0][1]=a[1],f[1][1]=b[1]对于i>=2，我们有f[0][i]=max(f[0][i-1]+b[i],f[1][i-1]+a[i])---(1)f[1][i]=max(f[0][i-1]+c[i],f[1][i-1]+b[i])---(2)假若我们已经知道了f[0][i-1]和f[1][i-1]，即在第i个位置没人和有人的情况下前i-1个机器能力值的最大对于f[0][i]而言， 即第i+1个机器上还没坐人时，那么考虑第i个机器和第i-1个机器有人的时间顺序如果第i个机器坐人后于第i-1个机器，那么必然坐第i个机器的能力值为b[i]，因为它左边有人右边没人对前i-1个机器，由于第i个机器后于第i-1个机器坐人，这时f[0][i]=f[0][i-1]+b[i]如果第i个机器坐人先于第i-1个机器坐人，那么f[0][i]=f[1][i-1]+a[i]同理对于f[1][i]， f[1][i]=max(f[0][i-1]+c[i],f[1][i-1]+b[i])，还是第i台和第i-1台机器坐人的顺序问题这样下去，由于第n台机器右边问题，故所求即为f[0][n] 
*/ 
#include<iostream>
using namespace std;
int f[2][10001],a[10001],b[10001],c[10001],n;
int main()
{cin>>n;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++) cin>>c[i];f[0][1]=a[1];f[1][1]=b[1];for(int i=2;i<=n;i++){f[0][i]=max(f[0][i-1]+b[i],f[1][i-1]+a[i]);f[1][i]=max(f[0][i-1]+c[i],f[1][i-1]+b[i]);}cout<<f[0][n];	 
}
/* version 2:上面的DP可能不是很好想，那么我们观察一下，对于每一个不是最左和最右的位置，都有四个状态：0. 左右没人，1.左有人右没人，2. 左没人右有人，3.左右有人，于是可以考虑将每一个点分为四个状态DP。f[i][0]:坐第i个机器时左右无人，于是左下后考虑前面i-1个机器，只需考察f[i-1][2]和f[i-1][3]f[i][1]:坐第i个机器时左有人右没人，于是先坐完前i-1个机器，只考察f[i-1][0]和f[i-1][1] 同理对f[i][2]和f[i][3]最后只需输出max(f[n][0],f[n][1])即可 
*/ 
#include<iostream>
using namespace std;
int f[10001][4],a[10001],b[10001],c[10001],n;
int main()
{cin>>n;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++) cin>>c[i];f[1][0]=a[1],f[1][2]=b[1];for(int i=2;i<=n;i++){f[i][0]=max(f[i-1][2],f[i-1][3])+a[i];f[i][1]=max(f[i-1][0],f[i-1][1])+b[i];f[i][2]=max(f[i-1][2],f[i-1][3])+b[i];f[i][3]=max(f[i-1][0],f[i-1][1])+c[i];}cout<<max(f[n][0],f[n][1]);
}