博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P2347 砝码称重 某一年noip提高组原题
阅读量:6719 次
发布时间:2019-06-25

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

可以转化为01背包求方案数的问题,dp数组f[][]表示第几个砝码能称出的重量,可压缩至一维 转移方程为f(i,j)+=f(i-1,j-w[i]) 当前我们可以称出的重量必定是由之前的砝码重量转移过来的

#include
using namespace std;const int N=550;const int maxn=1e6+7;int f[maxn];int a[maxn];int v[maxn];//相当于01背包的物品重量int num[10]={
0,1,2,3,5,10,20};//砝码重量int cnt; int maxsum;int ans;int main(){ for(int i=1;i<=6;i++) { scanf("%d",&a[i]); for(int j=1;j<=a[i];j++) { v[++cnt]=num[i];//统计 } } for(int i=1;i<=cnt;i++) { maxsum+=v[i];//背包的最大容量 } f[0]=1;//0也是一种方案,初始状态 for(int i=1;i<=cnt;i++)//01背包 { for(int j=maxsum;j>=v[i];j--) { f[j]+=f[j-v[i]]; } } for(int i=1;i<=maxsum;i++)//统计方案个数 { if(f[i]) { ans++; } } printf("Total=%d",ans); return 0;}

 

转载于:https://www.cnblogs.com/LJB666/p/10808631.html

你可能感兴趣的文章
Java 环境搭建
查看>>
软件体系架构阅读笔记十五
查看>>
启用了不安全的HTTP方法解决办法 IBM APPSCAN
查看>>
javascript小记-javascript运行机制
查看>>
汇编指令
查看>>
JVM调优——之CMS 常见参数解析
查看>>
深入.NET框架
查看>>
Android Studio实现Service AIDL
查看>>
模态混叠和端点效应
查看>>
数据库
查看>>
初始Hibernate框架
查看>>
js中math对象的使用
查看>>
写《一摞烙饼的排序》的代码关于架构有感
查看>>
beego 定义一个存储变量的容器
查看>>
[HDU5343]MZL's Circle Zhou
查看>>
不要妄想永远,只愿珍惜现在
查看>>
Centos 7 安装和配置Redis
查看>>
ajax的封装
查看>>
如何更改windows鼠标滚轮的方向,按滚动条,按手指(触摸屏操作模式),跟mac一样,以win7为例,在windows中使用mac鼠标模式...
查看>>
Mysql 数据库和Oracal数据库的连接
查看>>