AHOI2013 解题报告

AHOI2013 D1T1 找硬币

题目链接:Luogu P5228/BZOJ3233

题目限制

  • 时间限制:$1\texttt{s}$;
  • 空间限制:$512\texttt{MiB}$。

题目描述

小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为 $x_1,x_2,x_3,\cdots$,那么 $x_1$ 必须为 $1$,$x_b$ 必须为 $x_a$ 的正整数倍($b>a$)。例如 $\{1,5,125,250\}$ 就是一组合法的硬币序列,而 $\{1,5,100,125\}$ 就不是。不知从哪一天开始,可爱的蛇爱上了一种萌物——兔纸!从此,小蛇便走上了遇上兔纸娃娃就买的不归路。某天,小蛇看到了 $N$ 只可爱的兔纸,假设这 $N$ 只兔纸的价钱分别是 $a_1,a_2,\cdots,a_N$。现在小蛇想知道,在哪一组合法的硬币序列下,买这 $N$ 只兔纸所需要的硬币数最少。买兔纸时不能找零。

数据范围与提示

对于 $100\%$ 的数据,有 $1\leq N\leq 50$,$1\leq a_i\leq 10^5$。

题解

设 $f_i$ 表示以 $i$ 为最大面值时最少使用的货币个数。

枚举 $i\cdot j\leq\texttt{A}$,有 $f_{ij}=\min\{f_i-M\}$,其中 $M$ 为所有兔子中可以把 $j$ 个面值为 $i$ 的货币换成面值为 $i\cdot j$ 的货币时可以减少的货币数量。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        res = 10 * res + (ch ^ '0'), ch = getchar();
    return res;
}

const int MAXN = 50 + 5;
const int MAXA = 1e5 + 5;

int n;
int a[MAXN];
int dp[MAXA];

int main(void)
{
    n = read();
    int Max = 0;
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    for (reg int i = 1; i <= n; ++i)
    {
        a[i] = read();
        Max = max(Max, a[i]);
        dp[1] += a[i];
    }
    int ans = dp[1];
    for (reg int i = 1; i <= Max / 2; ++i)
    {
        for (reg int j = 2; j * i <= Max; ++j)
        {
            reg int sum = 0;
            for (reg int k = 1; k <= n; ++k)
                sum += a[k] / (i * j);
            dp[i * j] = min(dp[i * j], dp[i] - (j - 1) * sum);
            ans = min(ans, dp[i * j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}
Pages: 1 2 3 4 5 6 7 8