|
#2
rjsp2019-08-20 10:46
题目链接呢？
从某个位置起，共有三种取值方案，即： a. 不取 b. 取一个，不取 c. 取两个，不取 用递归写的话，非常简单，但运行效率一定很低，需要剪枝。 当到达某个位置时，不管是怎么来的，都只需要取“累加和”最大的就行（相当于剪枝）  程序代码：#include <cstdio> unsigned foo( const unsigned buf[], size_t n ) { unsigned record[3] = { 0, 0, 0 }; for( size_t i=0; i!=n; ++i ) { unsigned tmp = record[0]; record[0] = record[1]; record[1] = record[2]; { if( record[0] < tmp ) record[0] = tmp; } { if( record[1] < tmp+buf[i] ) record[1] = tmp+buf[i]; } if( i+1 < n ) { if( record[2] < tmp+buf[i]+buf[i+1] ) record[2] = tmp+buf[i]+buf[i+1]; } } return record[0]<record[1]?record[1]:record[0]; } int main( void ) { size_t n; unsigned buf[10000]; scanf( "%zu", &n ); for( size_t i=0; i!=n; ++i ) scanf( "%u", buf+i ); printf( "%u\n", foo(buf,n) ); } |
题目描述
从n个数中取出若干个数，可以连续取1个，也可以连续取2个，但连续取的数不能有3个或多于3个。问取到的最大的和是多少？
输入
第1行：一个整数n（1<=n<=10000）。
第2行：空格隔开的n个整数ai（1<=ai<=100000）。
输出
一行，1个整数，表示取到的最大和。
