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>

相關日誌