题目链接：http://codeforces.com/problemset/problem/358/D
开始题意理解错，整个就跪了= =
题目大意：从1到n的位置取数，取数的得到值与周围的数有没有取过有关，所有数都要取，求最终得到的最大结果
解题思路：dp题，转移方程如下
dp[i][0]=max(dp[i-1][0]+b[i-1],dp[i-1][1]+c[i-1])
dp[i][1]=max(dp[i-1][0]+a[i-1],dp[i-1][1]+b[i-1])
a,b,c分别表示周围没有数，有一个数，有两个数取过的情况。
dp[i][0]表示取i个位置时，i-1没取过的情况。（实际取数的情况，先i，再i-1）
dp[i][1]表示取i个位置时，i-1取过的情况。（实际取数的情况，先i-1，再i）
代码如下：
1 // 2013/10/26 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 #define N 3005 9 int a[N],b[N],c[N]; 10 int dp[N][2]; 11 int main() 12 { 13 int n,i; 14 memset(dp,0,sizeof(dp)); 15 scanf("%d",&n); 16 for(i=1;i<=n;i++){ 17 scanf("%d",&a[i]); 18 } 19 for(i=1;i<=n;i++) 20 scanf("%d",&b[i]); 21 for(i=1;i<=n;i++) 22 scanf("%d",&c[i]); 23 if(n==1) 24 cout<<a[1]<<endl; 25 else 26 { 27 dp[2][0]=b[1]; 28 dp[2][1]=a[1]; 29 // dp[i][0]表示i位置时(i-1)没喂过 30 // dp[i][1]表示i位置时(i-1)喂过 31 for(i=3;i<=n;i++) 32 { 33 dp[i][0]=max(dp[i-1][0]+b[i-1],dp[i-1][1]+c[i-1]); 34 //前者顺序n[i],n[i-1],n[i-2],后者顺序n[i-2],n[i],n[i-1] 35 dp[i][1]=max(dp[i-1][0]+a[i-1],dp[i-1][1]+b[i-1]); 36 //n[i-1],n[i-2],n[i];n[i-2],n[i-1],n[i] 37 } 38 int ans=max(dp[n][0]+a[n],dp[n][1]+b[n]); 39 cout<<ans<<endl; 40 } 41 return 0; 42 }