洛谷 P1450.硬币购物 解题报告

时间：2023-03-09 14:33:24
洛谷 P1450.硬币购物 解题报告

P1450.硬币购物

题目描述

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

输入输出格式

输入格式：

第一行 \(c_1,c_2,c_3,c_4,tot\) 下面\(tot\)行 \(d_1,d_2,d_3,d_4,s\)

输出格式：

每次的方法数

说明

\(di,s<=100000\)

\(tot<=1000\)

很容易想到的，转化成多重背包

		dp[0]=1;

        for(int i=1;i<=4;i++)

            for(int k=s;k>=0;k--)

                if(dp[k])

                    for(int j=1;j<=a[i];j++)

                        dp[k+j*c[i]]+=dp[k];

        printf("%d\n",dp[s]);

结果当然是\(t\)飞啦

如果我们当成完全背包来做的话，当放入物品个数大于限制条件时的一部分是非法的。

假设仅仅针对价值为\(c\)的物品\(i\),存在数量上限\(d\),要凑成的钱数为\(s\).

\(dp[s]\)为装无限个\(i\)时凑成\(s\)的方案数

\(dp[s-c*(d+1)]\)为装无限个\(i\)时凑成\(s-c*(d+1)\)的方案数

相减得到什么？ 不仅是装上限为\(d\)个时的方案数吗

然而这只是针对一个物品而言，如果有多个物品呢？

存在多个约束相交的情况，那么根据容斥原理，多的减，少的回加即可。

code：

#include <cstdio>

#define ll long long

const int N=100010;

int c[5],tot,a[5],s;

ll dp[N];

int main()

{

    for(int i=1;i<=4;i++) scanf("%d",c+i);

    scanf("%d",&tot);

    dp[0]=1;

    for(int i=1;i<=4;i++)

        for(int j=c[i];j<=N;j++)

            dp[j]+=dp[j-c[i]];

    while(tot--)

    {

        for(int i=1;i<=4;i++) scanf("%d",a+i);

        scanf("%d",&s);

        ll ans=0;

        for(int i=0;i<=15;i++)

        {

            int flag=0,t=0;

            for(int j=1;j<=4;j++)

                if((i>>j-1)&1)

                {

                    t+=c[j]*(a[j]+1);

                    flag^=1;

                }

            ll tt=(s>=t?dp[s-t]:0);

            ans+=(flag?-tt:tt);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

注意这时候枚举子集的方法。

2018.5.4

相关文章