14126: 【原4126】Spice and Wolf II

题目描述

author: 黄俊翔原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4126 ## Description

赫萝与罗伦斯正在米隆商行进口香辛料（胡椒），准备运到帕兹欧去卖掉。但米隆商行店大欺客，在找零时对于一崔尼银币以下的面额是一概不找的，因此赫萝希望在商行报价时能精确的给出所需的金额而无需找零。但是赫萝并不知道商行的报价会是多少，因此赫萝让罗伦斯拿出了身上所有的金币、银币和铜币。

这可是个大工程。因为中世纪时，有多个国家和商行都在发行货币，而且汇率还随着货币公信力经常变化，比现代货币还复杂。比方说，1卢米欧金币=24~40枚崔尼银币，1崔尼银币又能换到20+枚路德银币，1路德银币又能换3托里尤铜币（你看，1崔尼银币能换60+托里尤铜币，不给找零岂不是很坑）。这只是其中的四种货币，实际上当时同一个区域流通的货币种类甚至能达到几十种。所幸的是，所有的货币价值都是托里尤铜币的整数倍，因此所有的金额都可以用一个整数表示。

为了尽量节省找零的钱来买苹果，赫萝希望能算出罗伦斯能精确支付的金额有多少种。你能帮帮她吗？

Input Format

第一行包含一个正整数\(T\)，为测试数据的组数。

每组测试数据为两行。

第一行为两个正整数\(N, M\)，其中\(N\)代表总共有多少种钱币，而\(M\)则代表赫萝预期购买胡椒的总花费不会超过\(M\)枚托里尤铜币，因此她只需要知道\(M\)及以内的金额有多少种可以精确支付。

第二行为\(2N\)个正整数，格式为\(A_1, A_2, ..., A_N, C_1, C_2, ..., C_N\)。其中\(A_i\)表示第\(i\)种钱币相当于多少枚托里尤铜币，\(C_i\)表示第\(i\)种钱币有多少枚。

Output Format

每组测试数据对应输出一行，代表\(M\)枚托里尤铜币及以内的金额有多少种可以精确支付。

Sample Input

2
3 10
1 2 4 2 1 1
2 5
1 4 2 1

Sample Output

8
4

Data Range

对于\(30\%\)的数据，\(sum(C_i) \le 20\)。

对于\(60\%\)的数据，\(sum(C_i) \le 100\)。

对于额外\(20\%\)的数据，罗伦斯超级有钱，以至于对于任意的\(i\)都有\(A_i * C_i \ge M\)。友情提示1：罗伦斯不一定有托里尤铜币，请不要打输出\(M\)的主意。友情提示2：数据并不保证\(A_i * C_i < 2^{31} \approx 2 * 10^9\)。

对于\(100\%\)的数据，\(T \le 5\)，\(N \le 100\)，\(M,A_i,C_i \le 100000\)。

友情提示3：这次的正解还是30行。当然60分也是30行。80分约是30+10行。又是熟悉的30分骗分最长系列。

WashSwang's solution

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t,n,m,dp[100001],k,ans;
long long a[101],c[101];
void zeroone(int w)
{
    for (int i=m;i>=w;--i)
        if (dp[i-w]) dp[i]=1;
}
void complete(int w)
{
    for (int i=w;i<=m;++i)
        if (dp[i-w]) dp[i]=1;
}
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for (int j=0;j<n;++j) scanf("%lld",&a[j]);
        for (int j=0;j<n;++j) {
            scanf("%lld",&c[j]);
            if (a[j]*c[j]<m)
            {
                k=1;
                while (k<c[j])
                {
                    zeroone(k*a[j]);
                    c[j]-=k;
                    k*=2;
                }
                zeroone(c[j]*a[j]);
            }
            else
                complete(a[j]);
        }
        for (int j=1;j<=m;++j)
            if (dp[j]) ++ans;
        printf("%d\n",ans);
    }
    return 0;
}