2021.12.06 P1450 [HAOI2008]硬币购物(组合数学+抽屉原理+DP)
2021.12.06 P1450 [HAOI2008]硬币购物(组合数学+抽屉原理+DP)
https://www.luogu.com.cn/problem/P1450
题意:
共有 44 种硬币。面值分别为 \(c_1,c_2,c_3,c_4\)。
某人去商店买东西,去了 \(n\) 次,对于每次购买,他带了 \(d_i\) 枚 \(i\) 种硬币,想购买 \(s\) 的价值的东西。请问每次有多少种付款方法。
分析:
设有且仅有一种硬币,价值为 \(c\) ,有 \(d\) 枚。现在想买价值为 \(s\) 的东西,在不限硬币个数的情况下的方案数为 \(f_s\) ,超出 \(d\) 枚的方案分别是取 \(d+1\) 枚、取 \(d+2\) 枚、取 \(d+3\) 枚……如果现在强制取 \(d+1\) 枚,那么再往上添一毛钱都不行!因为我们最少就取了 \(d+1\) 枚价值为 \(c\) 的硬币。
\(d+1\) 枚硬币的价值为 \(c*(d+1)\) ,还剩下的价值为 \(s-c*(d+1)\) ,剩下的无论怎么取一定会超过 \(d\) 枚硬币的方案数为 \(f_{s-c*(d+1)}\) 。因为选取价值为 \(c*(d+1)\) 硬币的方案数为 \(1\) ,即选取 \(d+1\) 枚硬币,根据乘法原理得,选取超过 \(d\) 枚硬币大的方案数为
\(ans=1*f_{s-c*(d+1)}=f_{s-c*(d+1)}\) ,
则满足条件的方案数为 \(f_s-ans\) 。
设我们有两种硬币,价值分别为 \(c_i\) 、 \(c_j\) ,分别有 \(d_i\) 枚、 \(d_j\) 枚。现在依旧想买价值为 \(s\) 的东西,超出 \(d_i\) 的方案数为 \(f_{s-c_i*(d_i+1)}\) ,超出 \(d_j\) 的方案数为 \(f_{s-c_j*(d_j+1)}\) 。但是存在即超出 \(d_i\) 又超出 \(d_j\) ,这种情况的方案数为 \(f_{s-c_i*(d_i+1)-c_j*(d_j+1)}\) 。根据容斥原理得,超出的总方案数为
\(tot=f_{s-c_i*(d_i+1)}+f_{s-c_j*(d_j+1)}-f_{s-c_i*(d_i+1)-c_j*(d_j+1)}\) ,
则满足条件的方案数为 \(f_s-tot\) 。
代码如下:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=1e5+10;
int n,c[5],num[5],s,f[N];
signed main(){
IOS;
for(int i=1;i<=4;i++)cin>>c[i];
f[0]=1;
for(int i=1;i<=4;i++)for(int j=c[i];j<=N-10;j++)f[j]+=f[j-c[i]];
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=4;j++)cin>>num[j];cin>>s;
int ans=f[s];
for(int k=15;k>0;k--){
int flag=0,ki=k,tot=0,aim=0;
while(ki){
++aim;
if(ki&1)tot+=(num[aim]+1)*c[aim],flag^=1;
ki>>=1;
}
if(tot>s)continue;
if(flag)ans-=f[s-tot];
else ans+=f[s-tot];
}
cout<<ans<<endl;
}
return 0;
}
最新文章
- terminator 安装及使用
- VC++6.0使用OpenGL前的配置(必看)
- ajax data数据里面传一个json到后台的写法
- Python类库下载
- 失败的数据库迁移UDB
- 图解TCP/IP读书笔记(一)
- JavaWeb三大组件(Servlet,Filter,Listener 自己整理,初学者可以借鉴一下)
- json2.js参考
- C# 类型和变量
- 自动安装lnmp
- Servlet启动的时机
- Entity Framework Code First实现乐观并发
- TensorFlow的Bazel构建文件结构
- C# 今天时间 今天结束时间
- Codeforces 1137D Cooperative Game (看题解)
- SSH服务理论+实践
- MapReduce(五)
- centos7下zabbix4.0配置磁盘IO监控
- Sleeping会话导致阻塞原理(上)
- mongodump备份小量分片集群数据