首页 > 代码库 > Bucharest, Romania 2013 G Points DP
Bucharest, Romania 2013 G Points DP
题意:一条线上面有n个目标,每个目标有三个值,表示不取相邻的,取一个相邻的,取两个相邻的值,问你怎么选才能最大
解题思路:每个点有个5种情况dp,dp状态转移方程在程序里,
5种情况分别是 1) 不取 2) 取自己 3) 取自己和左边,4)取自己和右边,5)取自己和左右边
解题代码:
1 Name: 12901.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月16日 星期六 14时18分16秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 int dp[1000005][5];28 int a[3];29 int max3(int x, int y,int z)30 {31 if(y > x )32 x = y ;33 if(z > x )34 x = z ; 35 return x;36 }37 int main(){38 int n ;39 while(scanf("%d",&n)!= EOF)40 {41 int ans = 0 ;42 memset(dp,0,sizeof(dp));43 for(int i =1 ;i <= n;i ++)44 {45 scanf("%d %d %d",&a[0],&a[1],&a[2]); 46 dp[i][0] = max3(dp[i-1][0],dp[i-1][1],dp[i-1][2]); 47 dp[i][1] = dp[i-1][0] + a[0];48 if(i != 1)49 dp[i][2] = a[1] + max(dp[i-1][3],dp[i-1][4]);50 if(i != n)51 { 52 dp[i][3] = a[1] + dp[i-1][0];53 if(i !=1)54 dp[i][4] = a[2] + max(dp[i-1][3],dp[i-1][4]); 55 }56 for(int j = 0;j <= 4;j ++)57 { 58 //if(dp[i][j] > ans)59 // printf("%d %d %d\n",i,j,dp[i][j]);60 ans = max(dp[i][j],ans);61 }62 }63 printf("%d\n",ans);64 }65 return 0;66 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。