HAOI 2008 硬币购物

This post is written in Chinese. Please consider using Google Translate

原来背包问题还有这种解法,动态规划+容斥原理。由于有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>

Related posts