[ABC231E] Minimal payments

[ABC231E] Minimal payments - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目关键信息，a[i]是a[i-1]的倍数,a[1]=1;

举例一组数据：

3 129
1 10 100

显然可以有,2*100找零,100+3*10找零,或直接100+2*10+9.

故根据贪心的思想，我们要从大面额钱开始，小面额值结束。

又因为1 ≤ N ≤ 60，且互为倍数的条件，所有实际所需枚举的钱数肯定不多。

故我们令DP[要凑x钱][到第now张纸钱]=所需的最少纸钱数

根据上面的样例，比如 10元面值 处理 29元,则有两种方案，10*3>29或10*2<29;

令p=x/a[now],res=x%a[now];

不找零情况：则可dfs(res,now-1);

找零情况：如果res不为0，则可dfs(a[now]*(p+1)-x,now-1)，如果res=0，没必要强制找零；

结合记忆化dp：

ll dfs(ll x,int now)
{
    if(!x) return 0;
    if(now==1) return x;
    if(dp[x][now]) return dp[x][now];
    ll p=x/a[now],res=x%a[now];
    ll cost1=INF,cost2=INF;
    cost1=p+dfs(res,now-1);
    if(res) cost2=p+1+dfs(a[now]*(p+1)-x,now-1);
    return dp[x][now]=min(cost1,cost2);
}

当然开dp[x][now]也是种技巧：

unordered_map<unorderde<ll,ll>,ll > dp;是不行的

unordered_map<ll,unordered_map<ll,ll> > dp; 是行的

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=110;
//const int M=;
//const int inf=0x3f3f3f3f;     
const ll INF=0x3ffffffffffff;
int T,n;
ll x,a[N];
unordered_map<ll,unordered_map<ll,ll> > dp;
//unordered_map<unorderde<ll,ll>,ll > dp;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
ll dfs(ll x,int now)
{
    if(!x) return 0;
    if(now==1) return x;
    if(dp[x][now]) return dp[x][now];
    ll p=x/a[now],res=x%a[now];
    ll cost1=INF,cost2=INF;
    cost1=p+dfs(res,now-1);
    if(res) cost2=p+1+dfs(a[now]*(p+1)-x,now-1);
    return dp[x][now]=min(cost1,cost2);
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read();scanf("%lld",&x);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    printf("%lld",dfs(x,n));
    return 0;
}