博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 1709
阅读量:4681 次
发布时间:2019-06-09

本文共 993 字,大约阅读时间需要 3 分钟。

题意:已知有N个不同的砝码,求这N个不同砝码不能称量的重量

分析:与一般的母函数类似,只是还要多考虑一步,就是砝码并不定都放一边

for(int i=1;i<=n;i++)

{
for(int j=0;j<=maxn;j++)
{
if(j+p[i]<=maxn)
num1[j+p[i]]+=num[j];
num1[abs(j-p[i])]+=num[j];//核心部分都加了这么一句
}
for(int j=0;j<=maxn;j++)
num[j]=num1[j];
}

#include
#include
#include
using namespace std;int num1[10010],num[10010],n;int p[110],ans[11000],maxn;void solve(){ memset(num1,0,sizeof(num1)); memset(num,0,sizeof(num)); num1[0]=num[0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=maxn;j++) { if(j+p[i]<=maxn) num1[j+p[i]]+=num[j]; num1[abs(j-p[i])]+=num[j]; } for(int j=0;j<=maxn;j++) num[j]=num1[j]; }}int main(){ while(scanf("%d",&n)==1) { maxn=0; for(int i=1;i<=n;i++) { scanf("%d",&p[i]); maxn+=p[i]; } solve(); int c=0; for(int i=1;i<=maxn;i++) { if(num[i]==0) ans[c++]=i; } printf("%d\n",c); if(c!=0) { printf("%d",ans[0]); for(int i=1;i

 

 

转载于:https://www.cnblogs.com/nanke/archive/2011/11/02/2233677.html

你可能感兴趣的文章
html页面之间传值问题
查看>>
【微软混合现实】开始使用Unity-第一章:创建一个新的项目
查看>>
JS高级——eval
查看>>
软件测试人员是选择大公司好,还是选择小公司更好
查看>>
Spark的39个机器学习库
查看>>
Electron学习笔记(一)
查看>>
你真的了解[super ]关键字吗?
查看>>
Java并发编程:CountDownLatch、CyclicBarrier和Semaphore
查看>>
配置NRPE的通讯
查看>>
VS2005编译VTK5.10.1
查看>>
shp系列(一)——利用C++进行shp文件的读(打开)与写(创建)开言
查看>>
总结上海永辉云商高级前端职位面试题集
查看>>
中国计算机学会推荐国际学术会议和期刊目录
查看>>
文本元素
查看>>
各种可以远程
查看>>
对服务器的认识
查看>>
分治法实现1-N的数字按字典序全排列组合 Java语言
查看>>
ASP.NET几种清除页面缓存的方法
查看>>
序列化 与 反序列化
查看>>
7-23
查看>>