HAOI 2008 硬币购物

原来背包问题还有这种解法，动态规划+容斥原理。由于有tot次询问，如果对每次询问单独都做一次多重背包问题，会超时。有一种一次预处理，每次询问只有O(1)的神奇解法：容斥原理。

设F[i]为不考虑每种硬币的数量限制的情况下，得到面值i的方案数。则状态转移方程为

F[i]=Sum{F[i-C[k]] | i-C[k]>=0 且 k=1..4}

为避免方案重复，要以k为阶段递推，边界条件为F[0]=1，这样预处理的时间复杂度就是O(S)。

接下来对于每次询问，奇妙的解法如下：根据容斥原理，答案为得到面值S的超过限制的方案数 - 第1种硬币超过限制的方案数 - 第2种硬币超过限制的方案数 - 第3种硬币超过限制的方案数 - 第4种硬币超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。

当第1种硬币超过限制时，只要要用到D[1]+1枚硬币，剩余的硬币可以任意分配，所以方案数为 F[ S - (D[1]+1)*C[1] ]，当且仅当(S - (D[1]+1)*C[1])>=0，否则方案数为0。其余情况类似，每次询问只用问16次，所以询问的时间复杂度为O(1)。

/* 
 * Problem: HAOI2008 coin
 * Author: Guo Jiabao
 * Time: 2009.4.15 21:54
 * State: Solved
 * Memo: 动态规划 容斥原理
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=100001;
using namespace std;
int D[5],C[5],T,S;
long long F[MAXN],Ans;
void init()
{
	freopen("coin.in","r",stdin);
	freopen("coin.out","w",stdout);
	scanf("%d%d%d%d%d",&C[1],&C[2],&C[3],&C[4],&T);
}
inline long long Fn(int a)
{
	return a>=0?F[a]:0;
}
void printint64(long long a)
{
	int m=100000000;
	if (a<=m)
		printf("%dn",a);
	else
	{
		printf("%d",Ans/m);
		printf("%08dn",Ans%m);
	}
}
void solve()
{
	int i,j;
	F[0]=1;
	for (j=1;j<=4;j++)
		for (i=1;i<MAXN;i++)
			if (i-C[j]>=0)
				F[i] += F[i-C[j]];
	for (i=1;i<=T;i++)
	{
		scanf("%d%d%d%d%d",&D[1],&D[2],&D[3],&D[4],&S);
		Ans =Fn( S );
		Ans-=Fn( S - (D[1]+1)*C[1] );
		Ans-=Fn( S - (D[2]+1)*C[2] );
		Ans-=Fn( S - (D[3]+1)*C[3] );
		Ans-=Fn( S - (D[4]+1)*C[4] );
		Ans+=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] );
		Ans+=Fn( S - (D[1]+1)*C[1] - (D[3]+1)*C[3] );
		Ans+=Fn( S - (D[1]+1)*C[1] - (D[4]+1)*C[4] );
		Ans+=Fn( S - (D[2]+1)*C[2] - (D[3]+1)*C[3] );
		Ans+=Fn( S - (D[2]+1)*C[2] - (D[4]+1)*C[4] );
		Ans+=Fn( S - (D[3]+1)*C[3] - (D[4]+1)*C[4] );
		Ans-=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] - (D[3]+1)*C[3] );
		Ans-=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] - (D[4]+1)*C[4] );
		Ans-=Fn( S - (D[1]+1)*C[1] - (D[3]+1)*C[3] - (D[4]+1)*C[4] );
		Ans-=Fn( S - (D[2]+1)*C[2] - (D[3]+1)*C[3] - (D[4]+1)*C[4] );
		Ans+=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] - (D[3]+1)*C[3] - (D[4]+1)*C[4] );
		printint64(Ans);
	}
}
int main()
{
	init();
	solve();
	return 0;
}

<div class="MainText">

<a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=302" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=302</a>

<strong>硬币购物</strong>

<strong>【问题描述】</strong>

一共有 4 种硬币,面值分别为 c1,c2,c3,c4 。阿Q带着一些硬币去商店买东西，他带了d1枚第一种硬币,d2枚第二种硬币,d3枚第三种硬币,d4枚第四种硬币,若想买一个价值为s的东西,问阿Q有多少种付coins的方法。

比如 c={1,2,5,10},d={3,2,3,1},s=10,一共有4种方法:
10=1+1+1+2+5
10=1+2+2+5
10=5+5
10=10

注意,阿Q可能会去很多次商店,每次带的硬币数量和要买的东西价值可能不一样,你需要对每次都求出方法总数.

<strong>【数据输入】</strong>
<p align="left">输入文件的第一行是5个整数, c1,c2,c3,c4,tot 分别表示4种硬币的面值和阿Q去商店的次数,下面 tot 行 ,每行5个非负整数,d1,d2,d3,d4,s</p>

<strong>【数据输出】</strong>

输出有tot行,表示第i次付coins的方法总数,保证答案在int64/long long范围内

<strong>【输入样例】</strong>
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

<strong>【输出样例】</strong>
4
27

<strong>【数据范围】</strong>

（1）100%的数据,d1,d2,d3,d4,s&lt;=1,00,000

（2）30%的数据,tot&lt;=50

（3）100%的数据,tot&lt;=1000</div>

上次修改时间 2017-02-03

相关日志