Skip to content

11389: 【原1389】畅畅的牙签(改)

题目

题目描述

author: SamJia 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1389

题目描述

畅畅觉得以前的牙签不太好,所以跑到了一个奇怪的地方去买一些奇怪的牙签,但是这个地方太奇怪了,竟然会按照交易时所用的钞票数量收税,为了逃避高额的税款,畅畅在交易时需要想尽办法让交易所用的钞票总数(支付的钞票和找回的钞票数目之和)最少。

但是,正如你所预料的那样,畅畅的脑子又瓦特了,所以,这个活还是要交给你们来做了。

当然啦,因为这是个奇怪的地方,所以钞票面值又怎么能够正常呢?所以这里有如下面值钞票:1, 2, 6, 24, 120, 720, 5040, 40320, 362880

输入格式

输入只有一行,有一个数字,表示畅畅买的牙签的价格y(1<=y<=10000)

输出格式

输出一个整数,表示最少所用钞票总数。

Sample Input

23

Sample Output

2

样例解释

给了24,找回1

yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_Y 500010
#define N 9
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;
const int price[N] = {1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int y;
int f[MAX_Y];
int main() {
    scanf("%d", &y);
    memset(f, 0x3f3f3f3f, sizeof(f));
    f[0] = 0;
    for (register int i = 0; i < N; ++i)
        for (register int j = price[i]; j < MAX_Y; ++j)
            if (f[j - price[i]] < 0x3f3f3f3f)
                f[j] = min(f[j], f[j - price[i]] + 1);
    // for (register int i = 1; i < 25; ++i)
    //     printf("%d: %d\n", i, f[i]);
    int cur_min = 0x7fffffff;
    for (register int i = y; i < MAX_Y; ++i)
            cur_min = min(cur_min, f[i] + f[i - y]);
    printf("%d", cur_min);
    return 0;
}