HAOI 2008 硬幣購物

本文正體字版由OpenCC轉換

原來揹包問題還有這種解法，動態規劃+容斥原理。由於有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

相關日誌