洛谷P1450 [HAOI2008]硬币购物

题目描述

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。

输入输出格式

输入格式:

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

输出格式:

每次的方法数

输入输出样例

输入样例#1: 

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

输出样例#1:

4
27

说明

di,s<=100000

tot<=1000

[HAOI2008]

首先考虑如果去掉限制,那就是一个裸的完全背包问题

加上限制的话,我们可以考虑先求出没有限制的,再把超出限制的减去

体现到代码上,就是dp[num]减去dp[num-C[i]*(D[i]+1)]

这样每个都减去

但是会有减重的部分,再加回去

#include<iostream>
#include<cstdio>
#define LL long long 
using namespace std;
const LL MAXN=1e6+10;
LL C[5],S[5];
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline LL read()
{
    char c=nc();LL x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
LL dp[MAXN],ans;
void dfs(LL now,LL zt,LL num)
{
    if(num<0) return ;
    if(now==5)
    {
        if(zt&1) ans-=dp[num];
        else ans+=dp[num];
        return ;
    }
    dfs(now+1,zt+1,num-C[now]*(S[now]+1) );
    dfs(now+1,zt,num);
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    for(LL i=1;i<=4;i++) C[i]=read();
    dp[0]=1;
    for(LL i=1;i<=4;i++)
        for(LL j=C[i];j<=100001;j++)
                dp[j]+=dp[j-C[i]];
    LL K=read();
    while(K--)
    {
        for(LL i=1;i<=4;i++) S[i]=read();
        LL num=read();
        ans=0;
        dfs(1,0,num);
        printf("%lld\n",ans);
    
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

PKU POJ 1724 ROADS 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

7720
来自专栏程序员叨叨叨

8.3 入口函数

通常高级语言程序中只有一个入口函数,不过由于着色程序分为顶点程序和片断程序,两者对应着图形流水线上的不同阶段,所以这两个程序都各有一个入口函数。

19140
来自专栏编程

給 iOS 開發者的 python 學習日記十

写在前面 Python的基础语法在前段时间的穷追猛更后终于告一段落。今天来看看它的面向对象又有哪些奥秘呢? 标准的物件导向语言 Python。这里提供一个主观判...

25660
来自专栏大数据文摘

Python入门之数据处理——12种有用的Pandas技巧

24650
来自专栏木东居士的专栏

程序员该如何管理后宫:皇后造小人(工厂模式)

15720
来自专栏WindCoder

四则运算、幸福来敲门、求一次方程解ax+b=0

/* 功能:四则运算 日期:2013-03-16 */ #include<stdio.h> #include<stdlib.h>

7910
来自专栏Golang语言社区

麻将游戏数据结构和AI算法

用休息时间零零散散写完了网络麻将游戏,感觉其中有不少值得记录的东西。 基础数据结构     数据结构确定决定了程序的开发难易程度,就像是游戏的骨架,对于电脑AI...

1.2K20
来自专栏数据结构与算法

洛谷P4016 负载平衡问题(最小费用最大流)

题目描述 GG 公司有 nn 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时,只能在相...

37850
来自专栏蜉蝣禅修之道

CMU算法求网络瓶颈链路

19560
来自专栏数据结构与算法

ZR国庆Round2解题报告

然后刚T3暴力,刚完还有2h左右。。然后,,这时候我zz的选择去打T2的暴力,然而T2暴力真的不是一般的难写。。

13240

扫码关注云+社区

领取腾讯云代金券