SDUT 2766-小明传奇2(母函数)
2024-08-23 09:54:40
小明传奇2
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描写叙述
小明不但创建了自己的商店并且选择了建立了自己的货币系统。
传统地。一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。
小明想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其他。 写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数在0 到2^63-1之间。
输入
多组输入。输入到文件末。
货币系统中货币的种类数目是 V (1<=V<=25)。要构造的数量钱是 N (1<= N<=10,000)。
第一行: 二个整数,V 和 N 。
第二行: 可用的货币的面值 。
输出
单独的一行包括那个可能的用这v种硬币凑足n单位货币的方案数。
演示样例输入
3 10
1 2 5
演示样例输出
10
妥妥的母函数水过。。有点慢 跑了190MS
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#define maxn 10010
#define ll long long
#define INF 0x3f3f3f3f
#define pp pair<int,int>
using namespace std;
ll a[maxn],b[maxn],v[26],p,n;
void solve()
{
memset(a,0,sizeof(a));
a[0]=1;
for(int i=0;i<n;i++)
{
memset(b,0,sizeof(b));
for(int j=0;+j*v[i]<=p;j++)
for(int k=0;k+j*v[i]<=p;k++)
b[k+j*v[i]]+=a[k];
memcpy(a,b,sizeof(b));
}
printf("%lld\n",a[p]);
}
int main()
{
while(~scanf("%lld%lld",&n,&p))
{
for(int i=0;i<n;i++)
scanf("%lld",v+i);
solve();
}
return 0;
}
最新文章
- RadioStream应用源码完整版(iphone版和ipad版)
- C#设计模式学习资料--观察者模式
- Activity-在ListFragment中为ListView增加空白视图
- ubuntu studio
- 翻译题(map使用)
- Qt4_VS10 程序打包发布
- 文本面板——axure线框图部件库介绍
- 剖析Jetty实现原理
- 是男人就下100层【第四层】——Crazy贪吃蛇(1)
- 内容中断随想录(risc cpu的那些事)
- kettle连接Hive中数据导入导出(6)
- 前端bug记录
- redis出现错误:NOAUTH Authentication required.
- 自学Zabbix13.2 分布式监控proxy配置
- 许仙章鱼TV
- JAVA中equals方法与hashCode方法学习
- HDU2444 The Accomodation of Students
- InnoDB的锁机制浅析(三)—幻读
- 语法糖----C#的async和await
- Java基础(十):封装
热门文章
- 简述web工程师的职责与学习
- 第二步:开发工具Eclipse安装并汉化
- CentOS6.5升级autoconf版本,解决”Autoconf version 2.64 or higher is required“错误
- Javascript";怪异";现象
- react setState里的作用域
- Java线程同步:synchronized锁住的是代码还是对象
- DB Link
- centos7 安装LNMP(php7)之php7.0 yum安装
- Java 中 ConcurrentHashMap 原理分析
- [转载]JAVA调用Shell脚本