Pku 1032 Parliament

#include < stdio.h >

int result[ 500 ];

int main()

{

int n;

while ( scanf( " %d " , & n) != EOF )

{

int sum = 0 ;

int len = 0 ;

int value = 2 ;

while ( true ) {

sum += value;

result[len ++ ] = value ++ ;

if ( sum + value > n ) break ;

}

value -- ;

int left = n - sum;

if ( value == left )

{

for ( int i = 0 ; i < len; ++ i ) result[i] ++ ;

result[len - 1 ] ++ ;

}

else for ( int i = len - 1 ; i >= 0 , left > 0 ; i -- , left -- ) result[i] ++ ;

for ( int i = 0 ; i < len; ++ i )

{

if ( i == 0 ) printf( " %d " , result[i] );

else printf( " %d " , result[i] );

}

printf( " \n " );

}

return 0 ;

}

做法就是求出以2起始的最大连续自然数序列之和sum，使得sum的值不超过输入数n，
然后分情况讨论：

设此最大序列为2、3、……、w，则：

1。若剩余值（n-sum）等于w，则最后输出序列为：3、4、……、w、w+2，即将原最大序列每项加1，再将最后剩余的一个1加到最后一项上。

2。若剩余值（n-sum）小于w，则从序列的最大项i开始，从大到小依次将每项加1，直到剩余值用完。

posted on 2008-10-29 10:26 Darren 阅读(491) 评论(0) 编辑收藏引用所属分类: 动态规划

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: pku 1691 Painting A Board 状态压缩DP Pku 1276 Cash Machine Pku 1651 Multiplication Puzzle 矩阵连乘 Pku 1023 The Fun Number System Pku 1032 Parliament Pku 1046 Color Me Less Pku 1080 Human Gene Functions Pku 3096 Surprising Strings Pku 1745 Divisibility

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

留言簿(5)

随笔分类

ACMers

搜索

积分与排名

最新随笔

最新评论