poj1014-Dividing

发布时间:2016-12-10 14:59:33 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj1014-Dividing",主要涉及到poj1014-Dividing方面的内容,对于poj1014-Dividing感兴趣的同学可以参考一下。

http://poj.org/problem?id=1014 母函数 总价值value = ( i * ( num[ i ] ) ) ( i = 1,....6 )  A、如果value 为奇数,那么一定不能再分; B、如果value为偶数,那么只需要判断母函数x ^ ( value / 2 ) 的系数是不是为0 ,如果为0 ,那么就表示不能再分,否则可以再分; note: 由于num[ i ] 会很大,所以要用到一个定理:对于任意一种珠宝的个数,如果n >= 8 , 就可以将n 改写3(n为奇数,1不行),或者4(n为偶数),不然就可能会超时 #include<map> #include<set> #include<list> #include<cmath> #include<ctime> #include<deque> #include<stack> #include<bitset> #include<cstdio> #include<vector> #include<cstdlib> #include<cstring> #include<iomanip> #include<numeric> #include<sstream> #include<utility> #include<iostream> #include<algorithm> #include<functional> using namespace std ; int main() { int test = 1 , sum , t ; int a[ 20005 ] , b[ 20005 ] , num[ 10 ] ; while( 1 ) { sum = 0 ; for( int i = 1 ; i <= 6 ; ++i ) { scanf( "%d" , &num[ i ] ) ; if( num[ i ] >= 8 ) { if( num[ i ] % 2 ) num[ i ] = 3 ; else num[ i ] = 4 ; } sum += num[ i ] * i ; } if( sum == 0 ) break ; if( sum % 2 ) { printf( "Collection #%d:\nCan't be divided.\n\n" , test++ ) ; continue ; } memset( a , 0 , sizeof( a ) ) ; memset( b , 0 , sizeof( b ) ) ; a[ 0 ] = 1 ; t = sum / 2 ; for( int i = 1 ; i <= 6 ; ++i ) { for( int j = 0 ; j <= t ; ++j ) { for( int k = 0 ; k <= num[ i ] && k * i + j <= t ; ++k ) { b[ k * i + j ] += a[ j ] ; } } for( int j = 0 ; j <= t ; ++j ) { a[ j ] = b[ j ] ; b[ j ] = 0 ; } } if( !a[ t ] ) printf( "Collection #%d:\nCan't be divided.\n\n" , test++ ) ; else printf( "Collection #%d:\nCan be divided.\n\n" , test++ ) ; } return 0; }

上一篇:->
下一篇:mini2440驱动分析之LCD

相关文章

关键词: poj1014-Dividing

相关评论