首页 > 代码库 > zoj 3310 - Unrequited Love
zoj 3310 - Unrequited Love
题目:给你一个数字环,从里面去除不相邻的数字,使得取出的数字和最大。
分析:dp,动态规划。
如果没有首尾相连的话,这个题目就很简单了:
动态方程:F(n)= max(F[ n-1 ],F[ n-2 ] + D[ n ]);
现在告诉我们首尾相连,为了无后效性,我们要把环拆开。;
我们把第一个元素分为两种状况,取或不取:
当取第一个元素时,我们DP到n-1位置;当不取第一个元素时,我们DP到n位置;
时间复杂性:O(n)。
说明:(2011-09-19 09:26)。
#include <stdio.h> #include <string.h> int D[ 1000002 ]; int F[ 1000002 ]; int G[ 1000002 ]; int main() { int n; while ( ~scanf("%d",&n) ) { for ( int i = 1 ; i <= n ; ++ i ) scanf("%d",&D[ i ]); /* 当选择第一个数字时 */ memset( F, 0, sizeof( F ) ); F[ 1 ] = D[ 1 ]; for ( int i = 2 ; i <= n ; ++ i ) { F[ i ] = F[ i-2 ] + D[ i ]; if ( F[ i ] < F[ i-1 ] ) F[ i ] = F[ i-1 ]; } int Max = F[ n-1 ]; /* 当不选择第一个数字时 */ memset( G, 0, sizeof( F ) ); for ( int i = 2 ; i <= n ; ++ i ) { G[ i ] = G[ i-2 ] + D[ i ]; if ( G[ i ] < G[ i-1 ] ) G[ i ] = G[ i-1 ]; } if ( Max < G[ n ] ) Max = G[ n ]; printf("%d\n",Max); } return 0; }
zoj 3310 - Unrequited Love
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。