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个中是最后选的。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 int n,a[3005][3],f[3005][3][2]; 7 int read(){ 8 int t=0,f=1;char ch=getchar(); 9 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 10 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 11 return t*f; 12 } 13 int main(){ 14 int n=read(); 15 for (int j=0;j<=2;j++) 16 for (int i=1;i<=n;i++) 17 a[i][j]=read(); 18 for (int i=0;i<=n;i++) 19 for (int j=0;j<=2;j++) 20 for (int k=0;k<=1;k++) 21 f[i][j][k]=-0x3f3f3f3f; 22 f[1][1][1]=a[1][1]; 23 f[1][2][0]=f[1][1][0]=-0x3f3f3f3f; 24 f[1][0][0]=a[1][0]; 25 for (int i=2;i<=n;i++){ 26 f[i][0][0]=std::max(f[i-1][1][1]+a[i][0],f[i-1][2][0]+a[i][0]); 27 f[i][1][0]=std::max(f[i-1][1][0]+a[i][1],f[i-1][0][0]+a[i][1]); 28 f[i][1][1]=std::max(f[i-1][1][1]+a[i][1],f[i-1][2][0]+a[i][1]); 29 f[i][2][0]=std::max(f[i-1][1][0]+a[i][2],f[i-1][0][0]+a[i][2]); 30 } 31 int ans=0; 32 ans=f[n][1][0]; 33 ans=std::max(ans,f[n][0][0]); 34 printf("%d ",ans); 35 return 0; 36 }