AT_abc231_e 题解

ikunTLE · 2024-12-17 20:47:11 · 题解

题目传送门

思路

可以用贪心思想解决这道题。

首先发现 A 单调递增且 A_i 是 A_{i-1} 倍数，所以我们倒序遍历 A，对于 A_i，使其最接近所剩的 X 一定是最优的选择。

但是，对于找零和不找零两种情况，最优解暂时不能确定。需要分情况讨论当前步骤所需次数和剩下的钱：

• 如果不需要找零，那么当前所需使用的次数为 \lfloor\frac{X}{A_i}\rfloor，剩下的钱为 X\bmod A_i。
• 如果需要找零，次数即为不找零的次数 +1。需要用所付的钱减去剩下的钱，即为 A_i(\lfloor\frac{X}{A_i}\rfloor+1)-X。

不难发现，上述内容可以用搜索实现。

注意事项

• 不开 long long 见祖宗。
• 直接 dfs 会导致 TLE，记得记忆化。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=70;
int n,a[N];
map<int,map<int,int>>f;
int dfs(int x,int i){
    if(i==n)
        return x;
    if(f[x][i])//记忆化
        return f[x][i];
    int op1=x/a[i]+dfs(x%a[i],i+1);//不找零
    int op2=x/a[i]+1+dfs(a[i]*(x/a[i]+1)-x,i+1);//找零
    f[x][i]=min(op1,op2);//取最优解
    return f[x][i];
}
signed main(){
    n=read();
    int x=read();
    for(int i=n;i>=1;--i)//反转数组, 方便操作
        a[i]=read();
    printf("%lld\n",dfs(x,1));
    return 0;
}