BZOJ1097: [POI2007]旅游景点atr【背包+容斥】

1097: [POI2007]旅游景点atr

【题目描述】

传送门

【题解】

这题就是背包+容斥。
f[s]表示不考虑硬币个数的方案数。
f[s-c1*(d1+1)]表示1号硬币放多的方案数。
f[s]-一种硬币放多的方案数+二种硬币放多的方案数-三种硬币放多的方案数+四种硬币放多的方案数。

代码如下

#include<cstdio>
using namespace std;
const int tot=100000;
int n,c[10],d[10],s;long long f[100005],Ans;
long long get(int x1=0,int x2=0,int x3=0,int x4=0){
    if(s-c[x1]*(d[x1]+1)-c[x2]*(d[x2]+1)-c[x3]*(d[x3]+1)-c[x4]*(d[x4]+1)<0) return 0;
    return f[s-c[x1]*(d[x1]+1)-c[x2]*(d[x2]+1)-c[x3]*(d[x3]+1)-c[x4]*(d[x4]+1)];
}
int main(){
    scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&n);
    f[0]=1;
    for(int i=1;i<=4;i++)
    for(int j=c[i];j<=tot;j++) f[j]+=f[j-c[i]];
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s);
        Ans=get();
        Ans-=get(1)+get(2)+get(3)+get(4);
        Ans+=get(1,2)+get(1,3)+get(1,4)+get(2,3)+get(2,4)+get(3,4);
        Ans-=get(1,2,3)+get(1,2,4)+get(1,3,4)+get(2,3,4);
        Ans+=get(1,2,3,4);
        printf("%lld\n",Ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部