Posted on 2010-08-04 11:36
MiYu 阅读(771)
评论(0) 编辑 收藏 引用 所属分类:
ACM ( 母函数 )
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
题目地址 :
http://acm.hdu.edu.cn/showproblem.php?pid=1709
题目大意 :
母函数的题目, 听说也可以用DP 做, DP没学好, 所以不是很明白.
题目的意思就是: 给你N个砝码, 以及每个砝码的重量, 当然,每个
砝码
只有一个, 这是关键!! 我没理解好题目,就YM在这里了........
然后问用这几个砝码不能称出的重量有几种,并输出他们. 当然,
因为是天平,所以2边都可以放!
代码如下 :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include <iostream>
int wei[101];
int num1[10005];
int num2[10005];
int sum;
int main ()
{
int N;
while ( scanf ( "%d",&N ) != EOF )
{
sum = 0;
for ( int i = 1; i <= N; ++ i )
{
scanf ( "%d",&wei[i] );
sum += wei[i];
}
for ( int i = 0; i <= sum; ++ i )
{
num1[i] = 0;
num2[i] = 0;
}
num1[0] = 1;
for ( int i = 1; i <= N; ++ i )
{
for ( int j = 0; j + wei[i] <= sum; ++ j )
{
if ( num1[j] == 1 ) //判断砝码总重量 J 是否出现过
{
num2[j] = 1;
num2[ j + wei[i] ] = 1;
num2[ abs( j - wei[i] ) ] = 1;
}
}
if ( i + 1 > N )
{
break;
}
for ( int j = 0; j <= sum; ++ j )
{
num1[j] = num2[j];
num2[j] = 0;
}
}
int nCount = 0;
for ( int i = 1; i <= sum; ++ i )
{
if ( num2[i] == 0 )
{
num1[nCount ++] = i;
}
}
if ( nCount == 0 )
{
printf ( "0\n" );
}
else
{
printf ( "%d\n",nCount );
for ( int i = 0; i != nCount; ++ i )
{
if ( !i )
{
printf ( "%d",num1[i] );
}
else
{
printf ( " %d",num1[i] );
}
}
putchar ( '\n' );
}
}
return 0;
}