POJ Dollar Dayz 美元假日(完全背包,常规+大数)
2024-09-02 20:13:37
题意:给出整数n和k,n代表拥有的钱数量,k代表有k种工具,其价钱分别为1~k。求n元能有多少种购买的方案。
思路:k最大有100,数量过大,要用大数。其他的基本和完全背包一样。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int B=, N=;
int coin[], n, k; struct bign { //请先设置常数N作为缓冲区和最大整数的长度。
int len, sex;
int s[N]; bign() { //创建一个新的大数
this -> len = ;
this -> sex = ;
memset(s, , sizeof(s));
}
bign (int number) {*this = number;} //创建一个大数,用整型初始化
bign (const char* number) {*this = number;} //创建一个大数,用字符串初始化 void operator = (const char *number) { //重载等号,等于一个字符串
int begin = ;
len = ;
sex = ;
if (number[begin] == '-') {
sex = -;
begin++;
}
else if (number[begin] == '+')
begin++; for (int j = begin; number[j]; j++)
s[len++] = number[j] - '';
} bign operator = (int number) { //重载等号,等于一个整型
char str[N]; //注意这里的N,要设一个缓冲区在外面供使用。
sprintf(str, "%d", number);
*this = str;
return *this;
} bign change(bign cur) {
bign now;
now = cur;
for (int i = ; i < cur.len; i++)
now.s[i] = cur.s[cur.len - i - ];
return now;
} void delZore() { // 删除前导0.
bign now = change(*this);
while (now.s[now.len - ] == && now.len > ) {
now.len--;
}
*this = change(now);
} void put() { // 输出数值。
delZore();
if (sex < && (len != || s[] != ))
cout << "-";
for (int i = ; i < len; i++)
cout << s[i];
} bign operator + (const bign &cur){ //只能是大数operator大数
bign sum, a, b;
sum.len = ;
a = a.change(*this);
b = b.change(cur); for (int i = , g = ; g || i < a.len || i < b.len; i++){
int x = g;
if (i < a.len) x += a.s[i];
if (i < b.len) x += b.s[i];
sum.s[sum.len++] = x % ;
g = x / ;
}
return sum.change(sum);
} bign operator - (const bign &cur) { //只能是大数operator大数
bign sum, a, b;
sum.len = len;
a = a.change(*this);
b = b.change(cur); for (int i = ; i < b.len; i++) {
sum.s[i] = a.s[i] - b.s[i] + sum.s[i];
if (sum.s[i] < ) {
sum.s[i] += ;
sum.s[i + ]--;
}
}
for (int i = b.len; i < a.len; i++) {
sum.s[i] += a.s[i];
if (sum.s[i] < ) {
sum.s[i] += ;
sum.s[i + ]--;
}
}
return sum.change(sum);
}
}; void cal()
{
dp[]=;
for(int i=; i<=n; i++) dp[i]=; //初始化
int tmp=min(k,n); //k>n的部分买不起
for(int i=; i<tmp; i++)
for(int j=; j+coin[i]<=n; j++)
dp[j+coin[i]] = dp[j+coin[i]] + dp[j]; dp[n].put();
} int main() {
//freopen("input.txt", "r", stdin);
for(int i=; i<; i++) coin[i]=i+; //初始化
while(~scanf("%d%d",&n,&k))
cal();
return ;
}
AC代码
最新文章
- Ubuntu下用wireshark抓取802.11封包并进行过滤分析
- 使用Grunt 插件打包Electron Windows应用
- LeetCode 397. Integer Replacement
- iOS 在tableView上添加button导致按钮没有点击效果和不能滑动的 zhuang
- Graphics 导出图片使用【这个主要是画图类图的使用,记录一下】
- mysql-5.5.28源码安装过程中错误总结
- IOS时间戳
- ServiceBroker创建流程
- Action 操作
- java缓存算法【转】
- UVa 10054 The Necklace BFS+建模欧拉回路
- GDataXML的配置和使用
- Ubuntu apache 禁止目录浏览
- MySQL中的insert ignore into, replace into等的一些用法小结(转)
- Redis 上实现的分布式锁
- JS综合练习
- 如何修改script.bin/script.fex
- When to use next() and return next() in Node.js
- chordDiagramFromMatrix()函数与circos.link()函数结合绘制箭头线
- nmap工具简介