题意:一群菜鸡排成一排 分别给你 他和他边上的两个最先喂他 最后 喂他 第二喂他 菜鸡的高兴值 ,问你所有菜鸡的高兴值和最大是多少。
解题思路:dp[i][0-3] 分别代表四种情况。
解题代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 /************************************************************ 2 * Author : darkdream 3 * Email : darkdream1994@gmail.com 4 * Last modified : 2015-03-24 20:13 5 * Filename : 358d.cpp 6 * Description : 7 * *********************************************************/ 8 // File Name: 358d.cpp 9 // Author: darkdream 10 // Created Time: 2015年03月24日 星期二 18时51分20秒 11 12 #include<vector> 13 #include<list> 14 #include<map> 15 #include<set> 16 #include<deque> 17 #include<stack> 18 #include<bitset> 19 #include<algorithm> 20 #include<functional> 21 #include<numeric> 22 #include<utility> 23 #include<sstream> 24 #include<iostream> 25 #include<iomanip> 26 #include<cstdio> 27 #include<cmath> 28 #include<cstdlib> 29 #include<cstring> 30 #include<ctime> 31 #define LL long long 32 #define maxn 3005 33 using namespace std; 34 int dp[maxn][8]; 35 int c[maxn]; 36 int b[maxn]; 37 int a[maxn]; 38 int n; 39 int main(){ 40 scanf("%d",&n); 41 for(int i= 1;i <= n;i ++) 42 { 43 scanf("%d",&a[i]); 44 } 45 for(int i= 1;i <= n;i ++) 46 { 47 scanf("%d",&b[i]); 48 } 49 for(int i= 1;i <= n;i ++) 50 { 51 scanf("%d",&c[i]); 52 } 53 if(n != 1) 54 dp[1][2] = b[1]; 55 dp[1][3] = a[1]; 56 for(int i = 2; i< n;i ++) 57 { 58 dp[i][0] = max(dp[i-1][3],dp[i-1][1]) + c[i]; 59 dp[i][1] = max(dp[i-1][3],dp[i-1][1]) + b[i]; 60 dp[i][2] = max(dp[i-1][2],dp[i-1][0]) + b[i]; 61 dp[i][3] = max(dp[i-1][2],dp[i-1][0]) + a[i]; 62 } 63 if(n != 1 ) 64 { 65 dp[n][1] = max(dp[n-1][3],dp[n-1][1]) + b[n]; 66 dp[n][3] = max(dp[n-1][2],dp[n-1][0]) + a[n]; 67 } 68 /*for(int i = 1; i <= n;i ++) 69 { 70 for(int j = 0 ;j <= 3 ;j ++) 71 { 72 printf("%d ",dp[i][j]); 73 } 74 printf(" "); 75 }*/ 76 int mx = 0 ; 77 for(int i= 0 ;i<= 3 ;i ++) 78 mx = max(mx,dp[n][i]); 79 printf("%d ",mx); 80 return 0; 81 }