Posted on 2010-08-04 11:36
MiYu 閱讀(779)
評論(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;
}