poj 3181 Dollar Dayz

时间:2022-02-18 14:05:07
题意:给定一个数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的更多相关文章

  1. POJ 3181 Dollar Dayz&lpar;全然背包&plus;简单高精度加法&rpar;

    POJ 3181 Dollar Dayz(全然背包+简单高精度加法) id=3181">http://poj.org/problem?id=3181 题意: 给你K种硬币,每种硬币各自 ...

  2. POJ 3181 Dollar Dayz &amp&semi;&amp&semi; Uva 147 Dollars(完全背包)

    首先是 Uva 147:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_p ...

  3. poj 3181 Dollar Dayz(完全背包)

    Dollar Dayz Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5419   Accepted: 2054 Descr ...

  4. POJ 3181 Dollar Dayz(高精度 动态规划)

    题目链接:http://poj.org/problem?id=3181 题目大意:用1,2...K元的硬币,凑成N元的方案数. Sample Input 5 3 Sample Output 5 分析: ...

  5. poj 3181 Dollar Dayz &lpar;整数划分问题---递归+DP&rpar;

    题目:http://poj.org/problem?id=3181 思路:将整数N划分为一系列正整数之和,最大不超过K.称为整数N的K划分. 递归:直接看代码: 动态规划:dp[i][j]:=将整数i ...

  6. POJ 3181 Dollar Dayz DP

    f[i][j]=f[i-j][j]+f[i][j-1],结果很大需要高精度. //#pragma comment(linker, "/STACK:1024000000,1024000000& ...

  7. POJ 3181 Dollar Dayz (完全背包,大数据运算)

    题意:给出两个数,n,m,问1~m中的数组成n,有多少种方法? 这题其实就相当于 UVA 674 Coin Change,求解一样 只不过数据很大,需要用到高精度运算... 后来还看了网上别人的解法, ...

  8. POJ 3181 Dollar Dayz 简单DP

    这DP虽然简单 但是思考一下还是挺好的 题意是 1,2,3,4....k 用加法凑成N 每个数可取不限个数 令dp[i][j] 表示前i种数凑成j的方案数 然后dp[i][j] = dp[i - 1] ...

  9. poj 3181 Dollar Dayz(求组成方案的背包&plus;大数)

    可能nyist看见加的背包专题我老去凑热闹,觉得太便宜我了.他们新加的搜索专题居然有密码. 都是兄弟院校嘛!何必那么小气. 回到正题,跟我写的上一篇关于求组成方案的背包思路基本一样,无非就是一个二维费 ...

随机推荐

  1. CSS基础知识真难啊-font

    不吐不快啊!!!! 上午测试还好好的,下午再写一次准备发出来就出错了!! 传说中程序媛三大错觉:我肯定没错,刚才还好好的,一定是有人改了我代码.. 我的口头禅都快变成“刚刚还好好的”了! 事情是这样的 ...

  2. CentOS6&period;4安装mysql2redis

    1.安装apr 下载:http://apache.dataguru.cn//apr/apr-1.5.1.tar.gz tar zxvf apr-.tar.gz cd apr- vi configure ...

  3. php学习笔记4--php中的变量作用域

    变量作用域:可以简单地理解为变量的可见区域,变量能被访问的范围.如同其他语言,php中也有全局作用域和局部作用域之分,但是不同的是:php中的全局作用域指的是:只能在函数外部使用,而局部作用域指的是: ...

  4. C&num;验证类 可验证:邮箱&comma;电话&comma;手机&comma;数字&comma;英文&comma;日期&comma;身份证&comma;邮编&comma;网址&comma;IP &lpar;转&rpar;

    namespace YongFa365.Validator { using System; using System.Text.RegularExpressions; /**//// <summ ...

  5. WPF Command

    使用CustomControl时绑定Command用法 C# Part public static RoutedUICommand ClearCommand { get; private set; } ...

  6. 【Richard 的刷(水)题记录】

    大概想了想,还是有个记录比较好. 9/24 网络流一日游: 最大流:bzoj1711[Usaco2007 Open]Dining 拆点 BZOJ 3993 Sdoi2015 星际战争 二分 P.S.这 ...

  7. 厚着脸皮求领导写了一篇java小白进阶大牛之路!!!

    缘起&应朋友之邀 2019年已经过去两个月了,应朋友之邀,写写自己的个人经历,与其说经历还不如是自我的总结与反思.2012年2月份只身一人拖着行李箱来到北京库巴科技有限公司实习,那时候库巴处在 ...

  8. go使用websocket遇到dial&colon;x509&colon; certificate signed by unknown authority

    websocket.DefaultDialer.Dial(url, headers) 改为 websocket.Dialer{TLSClientConfig: &tls.Config{Root ...

  9. myeclipse中格式化代码快捷键Ctrl&plus;Shift&plus;F失效的解决办法

    任何软件快捷键失效99%的原因是跟其他软件的快捷键冲突了,经过检查,是跟搜狗输入法的简繁体切换快捷键Ctrl+Shift+F 冲突了,打开搜狗工具箱中的属性设置: 在属性设置中找到“按键”,将简繁体快 ...

  10. C&num;&lpar;Winform&rpar;中button的Enable&equals;false和visible的区别

    Enable:可用性 visible:可见性(不是visiable哦,没有这个单词) 如果设置了button或其他控件的Enable为false,还是能够看到控件,只是控件是灰色的,而且点不了: 但设 ...