AtCoder Beginner Contest 182 F - Valid payments

https://atcoder.jp/contests/abc182/tasks/abc182_f

 

题意:

有n种面值的货币a[i],满足a[i]是a[i-1]的倍数,a[1]=1

有一种价值为x的商品,付款y元,找零y-x元

问满足以下2个条件的y有多少种

条件1:付款和找零时,使用的货币数量在对应金额下最少

条件2:在满足条件1的前提下,付款所用的面值,找零时不能再使用

 

条件1即第i种面值的货币最多使用 a[i+1]/a[i] 次,且最大金额的货币不能用于找零

令mx[i]=a[i+1]/a[i]

 

每个数用所给的面值都有唯一的表达式

即w=k1*a1+k2*a2+……+kn*an,对于每个w来说,(k1,k2,……kn)是唯一的

将问题转化为给出x,求满足x+b=y,且b和y的ki不能同时非0

称ki为系数

将x+b=y用系数表示,再加上上界限制,即

   bk1  bk2  bk3  bk4……

+ xk1  xk2  xk3  xk4……

= yk1  yk2  yk3  yk4……

其中 0<=yki<mx[i],bki和yki不能同时非0

 

那么

如果bki非0,yki必须是0,所以bki满足 bki+xki+前一位的进位=mx[i]

如果bki=0,yki=xki+前一位的进位

所以当确定了是否进位后,bki是唯一的,相应的yki也是唯一的

 

dp[i][0/1]表示第i位是否进位(0不进位,1进位)的b的方案数(也是y的方案数)

 

如果当前位没有进位,

下一位一定可以没有进位

下一位如果想产生进位,对应xk必须非0 

因为如果下一位x的系数=0,要想产生进位必须b的系数=mx,而b的系数如果=mx就不满足条件1

 

如果当前位有进位,

下一位一定可以有进位

而下一位如果想没有进位,对应的xk必须满足加1不会产生进位

 

 

#include<cstdio>

typedef long long LL;

#define N 52

LL a[N];
LL mx[N],xx[N];
LL dp[N][2];

int main()
{
    int n;
    LL x,t;
    scanf("%d%lld",&n,&x);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    for(int i=1;i<n;++i) mx[i]=a[i+1]/a[i];
    t=x;
    for(int i=n;i;--i)
    {
        xx[i]=t/a[i];
        t%=a[i];
    }
    dp[1][0]=1;
    if(xx[1]) dp[1][1]=1;
    for(int i=1;i<n;++i)
    {
        dp[i+1][0]=dp[i][0];
        if(xx[i+1]) dp[i+1][1]=dp[i][0];
        dp[i+1][1]+=dp[i][1];
        if(xx[i+1]+1!=mx[i+1]) dp[i+1][0]+=dp[i][1];
    }
    printf("%lld",dp[n][0]);
}

 

上一篇:AtCoder Beginner Contest 097


下一篇:Java applet没有完全刷新