Posted on 2010-08-04 11:36
MiYu 閱讀(779)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM ( 母函數(shù) )
//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址 :
http://acm.hdu.edu.cn/showproblem.php?pid=1709
題目大意 :
母函數(shù)的題目, 聽(tīng)說(shuō)也可以用DP 做, DP沒(méi)學(xué)好, 所以不是很明白.
題目的意思就是: 給你N個(gè)砝碼, 以及每個(gè)砝碼的重量, 當(dāng)然,每個(gè)
砝碼
只有一個(gè), 這是關(guān)鍵!! 我沒(méi)理解好題目,就YM在這里了........
然后問(wèn)用這幾個(gè)砝碼不能稱出的重量有幾種,并輸出他們. 當(dāng)然,
因?yàn)槭翘炱?所以2邊都可以放!
代碼如下 :
//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
#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 是否出現(xiàn)過(guò)
{
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;
}