首页 > 代码库 > hdu 1709 The Balance（母函数）
hdu 1709 The Balance（母函数）
题意：
有一个天平。有N个砝码。重量分别是A1...AN。
问重量【1..S】中有多少种重量是无法利用这个天平和这些砝码称出来的。
S是N个砝码的重量总和。
思路：
对于每一个砝码来说，有三种：不放，放左盘，放右盘。
额，，母函数和DP其实核心一样，，，，
看代码，，
代码：
int n;int aa[105];bool a[10005], b[10005];int temp[10005];int main(){ while(scanf("%d",&n)!=EOF){ int tot=0; rep(i,1,n){ scanf("%d",&aa[i]); tot+=aa[i]; } mem(a,false); mem(b,false); a[0]=true; rep(i,1,n){ mem(b,false); rep(k,0,tot){ if(a[k]==true){ b[k]=true; if(k+aa[i]<=tot){ b[k+aa[i]]=true; } if(abs(k-aa[i])<=tot){ b[abs(k-aa[i])]=true; } } } rep(k,0,tot) a[k]=b[k]; } int ans=0; rep(i,0,tot){ if(a[i]==false){ temp[++ans]=i; } } printf("%d\n",ans); if(ans>0){ printf("%d",temp[1]); rep(i,2,ans) printf(" %d",temp[i]); cout<<endl; } } return 0;}
hdu 1709 The Balance（母函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。