bzoj1042: [HAOI2008]硬币购物（DP+容斥）

时间：2021-11-12 12:52:06

　　1600+人过的题排#32还不错嘿嘿

　　浴谷夏令营讲过的题，居然1A了

　　预处理出f[i]表示购买价值为i的东西的方案数

　　然后每次询问进行一次容斥，答案为总方案数-第一种硬币超限方案-第二种超限方案-第三种超限方案-第四种超限方案+第一种和第二种硬币超限方案+...

　　第i种硬币超限方案就是f[s-c[i]*(d[i]+1)]，其他的类推一下就行了

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,mx;

ll ans;

int c[],d[maxn][],s[maxn];

ll f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void dfs(int fir,int dep,int sum,int last)

{

    for(int i=last;i<=;i++)

    {

        if(sum+c[i]*(d[fir][i]+)>s[fir])continue;

        if(dep&)ans-=f[s[fir]-sum-c[i]*(d[fir][i]+)];

        else ans+=f[s[fir]-sum-c[i]*(d[fir][i]+)];

        dfs(fir,dep+,sum+c[i]*(d[fir][i]+),i+);

    }

}

int main()

{

    for(int i=;i<=;i++)read(c[i]);read(n);

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=;j++)read(d[i][j]);

        read(s[i]);mx=max(mx,s[i]);

    }

    f[]=;

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

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

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

    for(int i=;i<=n;i++)

    {

        ans=f[s[i]];

        dfs(i,,,);

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

    }

    return ;

}

相关文章