EOJ 3507 坑爹的售票机

问题描述

oxx 和 xjj 决定和小伙伴们一同坐船前往 Xiamen。去 Xiamen 的船票一张 p 元。

当他们满怀兴致地来到港口时发现居然只有不设找零的自动售票机，只能使用一元，五元，十元，二十元，五十元，一百元的纸币，且一次至多买 k 张船票。因此他们不得不去银行取钱。而 oxx 是个大懒人，他希望取的纸币数量越少越好，因此他想知道他们一行 n 人要都买到票至少需要取多少张纸币。
Input

第一行三个整数 n,k,p (1≤n≤10³,1≤k≤10,1≤p≤10³) 分别表示 oxx 需要购买船票张数，一次至多买船票数量，单张船票价格。
Output

输出一个整数，表示 oxx 至少要取多少张纸币。

题意即为：取钱n*p元，而一次至多取k张，问怎么取，使总共取的纸币张数最少

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define inf 10e8

int cost[]={,,,,,};

int dp[],now[]={};

int min(int a,int b)

{

    if(a<b)return a;

    return  b;

}

int main(int argc, const char * argv[])

{

    int n,k,p;

    scanf("%d%d%d",&n,&k,&p);

    //需要购买船票张数，一次至多买船票数量，单张船票价格。

    for(int i=;i<=k;++i)

    {

        int money=i*p;

        for(int j=;j>=;--j)

        {

            now[i]+=money/cost[j];

            money%=cost[j];

        }

        //计算需要多少张纸币

    }

    for(int i=;i<=n;++i)dp[i]=inf;

//    memset(dp,inf,sizeof(dp));

//    for(int i=1;i<=n;++i)std::cout<<dp[n]<<" ";

    for(int i=;i<=k;++i)

    {

        for(int j=i;j<=n;++j)

        {

            dp[j]=min(dp[j],dp[j-i]+now[i]);

        }

    }

    std::cout<<dp[n];

    puts("");

    return ;

}

巴特西

eoj 3507 坑爹的售票机

EOJ 3507 坑爹的售票机

最新文章

热门文章