http://codeforces.com/contest/358/problem/D
题意:给出n个数，每个数取走的贡献与相邻的数有关，如果取这个数的时候，左右的数都还没被取，那么权值为a，如果左右两个数有一个被取走了，那么权值为b，如果左右两个数都被取走了，那么权值为c，求取取走全部数的最大值。
思路:f[i][1][0]代表这个位置在i-1选后才选，f[i][1][1]代表这个位置在i+1选后才选，f[i][0][0]代表这个位置在3个中是第一个选的，f[i][2][0]代表这个位置在3个中是最后选的。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
int n,a[][],f[][][];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int main(){
int n=read();
for (int j=;j<=;j++)
for (int i=;i<=n;i++)
a[i][j]=read();
for (int i=;i<=n;i++)
for (int j=;j<=;j++)
for (int k=;k<=;k++)
f[i][j][k]=-0x3f3f3f3f;
f[][][]=a[][];
f[][][]=f[][][]=-0x3f3f3f3f;
f[][][]=a[][];
for (int i=;i<=n;i++){
f[i][][]=std::max(f[i-][][]+a[i][],f[i-][][]+a[i][]);
f[i][][]=std::max(f[i-][][]+a[i][],f[i-][][]+a[i][]);
f[i][][]=std::max(f[i-][][]+a[i][],f[i-][][]+a[i][]);
f[i][][]=std::max(f[i-][][]+a[i][],f[i-][][]+a[i][]);
}
int ans=;
ans=f[n][][];
ans=std::max(ans,f[n][][]);
printf("%d\n",ans);
return ;
}