[BZOJ 1042][HAOI 2008]コインショッピング(リュックサック+反発原理)
1682 ワード
タイトルリンク:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1042
最初は反発原理をやったばかりで、まだ少し骨が折れるので、私は弱すぎます...
まずバックパックに類似したDPで前処理を行い,各硬貨の個数に制限がないと仮定してf[i]=湊面値iのスキーム総数を求める.
しかし実際のテーマではコインの個数に制限があり、4種類のコインをそれぞれa、b、c、dとし、顔値Sのシナリオで制限を超えたシナリオ数=aが制限を超えたシナリオ数+bが制限を超えたシナリオ数+cが制限を超えたシナリオ数+dが制限を超えたシナリオ数-aとbが制限を超えたシナリオ数-aとcが制限を超えたシナリオ数...-cとdが制限を超えたシナリオ数+a,b,cが制限を超えたシナリオ数+a,c,dがいずれも制限を超えたシナリオ数+a,b,dいずれも制限を超えたシナリオ数+b,c,dがいずれも制限を超えたシナリオ数-abcdがいずれも制限を超えたシナリオ数
そしてDFSを尋ねるたびに,反発原理で解決すればよいが,dfsではkをマークし,現在の状況がプラスかマイナスかを示す.
注:dfsのi番目の硬貨の場合、i番目の硬貨がd[i]+1個使用されると、i番目の硬貨が制限を超えていることを意味し、残りの硬貨はi番目の硬貨の個数の制限を受けずに自由に分配することができる.
最初は反発原理をやったばかりで、まだ少し骨が折れるので、私は弱すぎます...
まずバックパックに類似したDPで前処理を行い,各硬貨の個数に制限がないと仮定してf[i]=湊面値iのスキーム総数を求める.
しかし実際のテーマではコインの個数に制限があり、4種類のコインをそれぞれa、b、c、dとし、顔値Sのシナリオで制限を超えたシナリオ数=aが制限を超えたシナリオ数+bが制限を超えたシナリオ数+cが制限を超えたシナリオ数+dが制限を超えたシナリオ数-aとbが制限を超えたシナリオ数-aとcが制限を超えたシナリオ数...-cとdが制限を超えたシナリオ数+a,b,cが制限を超えたシナリオ数+a,c,dがいずれも制限を超えたシナリオ数+a,b,dいずれも制限を超えたシナリオ数+b,c,dがいずれも制限を超えたシナリオ数-abcdがいずれも制限を超えたシナリオ数
そしてDFSを尋ねるたびに,反発原理で解決すればよいが,dfsではkをマークし,現在の状況がプラスかマイナスかを示す.
注:dfsのi番目の硬貨の場合、i番目の硬貨がd[i]+1個使用されると、i番目の硬貨が制限を超えていることを意味し、残りの硬貨はi番目の硬貨の個数の制限を受けずに自由に分配することができる.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define MAXN 100050
using namespace std;
typedef long long int LL;
LL ans=0;
LL f[MAXN];
int c[5],d[5];
void dfs(int x,int k,int sum) // x , sum ,k
{
if(sum<0) return;
if(x==5)
{
if(k&1) ans-=f[sum];
else ans+=f[sum];
return;
}
dfs(x+1,k+1,sum-(d[x]+1)*c[x]);
dfs(x+1,k,sum);
}
int main()
{
for(int i=1;i<=4;i++) scanf("%d",&c[i]);
int T;
scanf("%d",&T);
f[0]=1;
for(int k=1;k<=4;k++) // f[i]= , i , , k
for(int i=c[k];i<MAXN;i++)
f[i]+=f[i-c[k]];
for(int i=1;i<=T;i++)
{
for(int i=1;i<=4;i++) scanf("%d",&d[i]);
int x; // x
ans=0;
scanf("%d",&x);
dfs(1,0,x);
printf("%lld
",ans);
}
return 0;
}