Bakser's Blog

我是逗比。

bzoj1042 容斥原理+dp

| Comments

扔代码就跑

bzoj1042
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long LL;
#define N 100001
LL f[N],ans;
int c[4],tot,d[4],s;
inline void dfs(bool flag,int last,int sum)
{
    if(last>=5||sum<0)return;
    flag?ans-=f[sum]:ans+=f[sum];
    for(int i(last);i<4;i++)
        dfs(flag^1,i+1,sum-c[i]*(d[i]+1));
}
int main()
{
    for(int i(0);i<4;i++)
        scanf("%d",c+i);
    f[0]=1;
    for(int i(0);i<4;i++)
        for(int j(c[i]);j<N;j++)
            f[j]+=f[j-c[i]];
    scanf("%d",&tot);
    while(tot--)
    {
        ans=0;
        for(int i(0);i<4;i++)
            scanf("%d",d+i);
        scanf("%d",&s);
        dfs(0,0,s);
        printf("%llu\n",ans);
    }
    return 0;
}

Comments

comments powered by Disqus