[BZOJ1042/Luogu1450][HAOI2008]硬币购物(动态规划,容斥原理)

发布于 2018-04-03  71 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1042/Luogu1450][HAOI2008]硬币购物(动态规划,容斥原理)

Description

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

Tag

动态规划,容斥原理

解决思路

考虑当没有硬币的数量限制时怎么做,设\(F[i][j]\)表示前i种硬币凑出j元的方案数,这个可以用类似背包的方式预处理出来。

for (int i=0;i<4;i++)//枚举四种硬币
    {
        F[i][0]=0;
        for (int j=1;j<c[i];j++) F[i][j]=F[max(i-1,0)][j];//对于小于面值的,直接转移
        F[i][c[i]]=F[max(i-1,0)][c[i]]+1;
        for (int j=c[i]+1;j<=maxW;j++)
            F[i][j]=F[max(i-1,0)][j]+F[i][max(j-c[i],(ull)0)];
    }

然后考虑限制了数量怎么做。无非是不限制数量的-强制一种一定超过限制+强制两种一定超过限制-强制三种+强制四种。利用容斥原理求解。

至于如何强制某一种面值为i硬币一定购买c个呢?用总数减去i*c就可以得到了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ull unsigned long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const int maxW=100000;
const int inf=2147483647;

int n;
ull c[4];
ull d[4];
ull F[4][maxN];

int main()
{
    ios::sync_with_stdio(false);

    cin>>c[0]>>c[1]>>c[2]>>c[3];
    for (int i=0;i<4;i++)//预处理
    {
        F[i][0]=0;
        for (int j=1;j<c[i];j++) F[i][j]=F[max(i-1,0)][j];
        F[i][c[i]]=F[max(i-1,0)][c[i]]+1;
        for (int j=c[i]+1;j<=maxW;j++)
            F[i][j]=F[max(i-1,0)][j]+F[i][max(j-c[i],(ull)0)];
    }
    F[3][0]=1;//注意这里
    int Q;cin>>Q;
    while (Q--)//回答询问
    {
        ull s;
        cin>>d[0]>>d[1]>>d[2]>>d[3]>>s;
        ull Ans=0;
        for (int S=0;S<(1<<4);S++)//容斥原理
        {
            int w=s;int opt=1;
            for (int i=0;i<4;i++) if ((S&(1<<i))!=0) w-=c[i]*(d[i]+1),opt=-opt;
            if (w<0) continue;//当强制购买的超过限额,直接continue,因为此时不合法
            Ans=Ans+opt*F[3][w];
        }
        cout<<Ans<<endl;
    }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1042/Luogu1450][HAOI2008]硬币购物(动态规划,容斥原理)


HNCJ OIer