题解：AT_cpsco2019_s1_c Coins

lailai0916 · 2023-05-31 22:36:10 · 题解

题意简述

有 20 种硬币，面值分别为 1,10,100,\dots,10^9 和 5,50,500,\dots,5\times 10^9，每种硬币数量充足。

给定 n 种水果，每种的价格为 a_i。求任意买 k 种水果，使用硬币的最少个数。

解题思路

对于价格的每一位，为了让使用硬币的个数尽可能少，显然最优方案是使用相同位数的硬币。

我们将相同位数以 1 开头的硬币称为 硬币 A，以 5 开头的硬币称为 硬币 B。

设某位上的值为 x，分两种情况考虑：

• 若 x<5，使用 x 个硬币 A 即可；
• 若 x\ge5，将 5 个硬币 A 换成 1 个硬币 B，可节省 4 个硬币。

数据范围 k\le6，即最多选择 6 种水果。由于数据较小，可以直接递归枚举选取的水果，计算最终使用硬币的个数并取最小值。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=35;
int n,k,ans=inf;
int a[N];
void f(int u,int t,int s)
{
    if(t==k)
    {
        int sum=0;
        while(s)
        {
            if(s%10>=5)sum-=4;
            sum+=s%10;
            s/=10;
        }
        ans=min(ans,sum);
        return;
    }
    if(u>n)return;
    for(int i=0;i<2;i++)
    {
        if(t+i>k)continue;
        f(u+1,t+i,s+i*a[u]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    f(1,0,0);
    cout<<ans<<'\n';
    return 0;
}