题意:给定一个数p,要求用K种币值分别为1,2,3...K的硬币组成p,问方案数,1,2,2和2,2,1算一种方案即与顺序无关,n <= 1000,k <= 100
// 用完全背包做了 这题也是母函数题目了 #include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 1010
int dp[maxn][];
void Add(int n,int m){ int i;
for(i=;i<;i++){
dp[n][i]=dp[n][i]+dp[m][i];
if(dp[n][i]>=)
dp[n][i]%=,dp[n][i+]++;
}
}
int main()
{
int N,K;
while(scanf("%d %d",&N,&K)!=EOF){
int i,j;
memset(dp,,sizeof(dp));
dp[][]=;
for(i=;i<=K;i++)
for(j=i;j<=N;j++)
Add(j,j-i);//dp[j]+=dp[j-i]; 想都没想 就这么写 这么提交了 高精度啊 不WA 才怪
// printf("%d\n",dp[N]);
for(i=;i>=;i--) if(dp[N][i]) break;
for(;i>=;i--)printf("%d",dp[N][i]);
printf("\n");
}
return ;
}
poj 3181 Dollar Dayz的更多相关文章
-
POJ 3181 Dollar Dayz(全然背包+简单高精度加法)
POJ 3181 Dollar Dayz(全然背包+简单高精度加法) id=3181">http://poj.org/problem?id=3181 题意: 给你K种硬币,每种硬币各自 ...
-
POJ 3181 Dollar Dayz &;&; Uva 147 Dollars(完全背包)
首先是 Uva 147:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_p ...
-
poj 3181 Dollar Dayz(完全背包)
Dollar Dayz Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5419 Accepted: 2054 Descr ...
-
POJ 3181 Dollar Dayz(高精度 动态规划)
题目链接:http://poj.org/problem?id=3181 题目大意:用1,2...K元的硬币,凑成N元的方案数. Sample Input 5 3 Sample Output 5 分析: ...
-
poj 3181 Dollar Dayz (整数划分问题---递归+DP)
题目:http://poj.org/problem?id=3181 思路:将整数N划分为一系列正整数之和,最大不超过K.称为整数N的K划分. 递归:直接看代码: 动态规划:dp[i][j]:=将整数i ...
-
POJ 3181 Dollar Dayz DP
f[i][j]=f[i-j][j]+f[i][j-1],结果很大需要高精度. //#pragma comment(linker, "/STACK:1024000000,1024000000& ...
-
POJ 3181 Dollar Dayz (完全背包,大数据运算)
题意:给出两个数,n,m,问1~m中的数组成n,有多少种方法? 这题其实就相当于 UVA 674 Coin Change,求解一样 只不过数据很大,需要用到高精度运算... 后来还看了网上别人的解法, ...
-
POJ 3181 Dollar Dayz 简单DP
这DP虽然简单 但是思考一下还是挺好的 题意是 1,2,3,4....k 用加法凑成N 每个数可取不限个数 令dp[i][j] 表示前i种数凑成j的方案数 然后dp[i][j] = dp[i - 1] ...
-
poj 3181 Dollar Dayz(求组成方案的背包+大数)
可能nyist看见加的背包专题我老去凑热闹,觉得太便宜我了.他们新加的搜索专题居然有密码. 都是兄弟院校嘛!何必那么小气. 回到正题,跟我写的上一篇关于求组成方案的背包思路基本一样,无非就是一个二维费 ...
随机推荐
-
CSS基础知识真难啊-font
不吐不快啊!!!! 上午测试还好好的,下午再写一次准备发出来就出错了!! 传说中程序媛三大错觉:我肯定没错,刚才还好好的,一定是有人改了我代码.. 我的口头禅都快变成“刚刚还好好的”了! 事情是这样的 ...
-
CentOS6.4安装mysql2redis
1.安装apr 下载:http://apache.dataguru.cn//apr/apr-1.5.1.tar.gz tar zxvf apr-.tar.gz cd apr- vi configure ...
-
php学习笔记4--php中的变量作用域
变量作用域:可以简单地理解为变量的可见区域,变量能被访问的范围.如同其他语言,php中也有全局作用域和局部作用域之分,但是不同的是:php中的全局作用域指的是:只能在函数外部使用,而局部作用域指的是: ...
-
C#验证类 可验证:邮箱,电话,手机,数字,英文,日期,身份证,邮编,网址,IP (转)
namespace YongFa365.Validator { using System; using System.Text.RegularExpressions; /**//// <summ ...
-
WPF Command
使用CustomControl时绑定Command用法 C# Part public static RoutedUICommand ClearCommand { get; private set; } ...
-
【Richard 的刷(水)题记录】
大概想了想,还是有个记录比较好. 9/24 网络流一日游: 最大流:bzoj1711[Usaco2007 Open]Dining 拆点 BZOJ 3993 Sdoi2015 星际战争 二分 P.S.这 ...
-
厚着脸皮求领导写了一篇java小白进阶大牛之路!!!
缘起&应朋友之邀 2019年已经过去两个月了,应朋友之邀,写写自己的个人经历,与其说经历还不如是自我的总结与反思.2012年2月份只身一人拖着行李箱来到北京库巴科技有限公司实习,那时候库巴处在 ...
-
go使用websocket遇到dial:x509: certificate signed by unknown authority
websocket.DefaultDialer.Dial(url, headers) 改为 websocket.Dialer{TLSClientConfig: &tls.Config{Root ...
-
myeclipse中格式化代码快捷键Ctrl+Shift+F失效的解决办法
任何软件快捷键失效99%的原因是跟其他软件的快捷键冲突了,经过检查,是跟搜狗输入法的简繁体切换快捷键Ctrl+Shift+F 冲突了,打开搜狗工具箱中的属性设置: 在属性设置中找到“按键”,将简繁体快 ...
-
C#(Winform)中button的Enable=false和visible的区别
Enable:可用性 visible:可见性(不是visiable哦,没有这个单词) 如果设置了button或其他控件的Enable为false,还是能够看到控件,只是控件是灰色的,而且点不了: 但设 ...