题目链接:Click
here~~
母函数第三题。
题意是给你一定数目的1,2,5分的硬币,让你找出不能被这些硬币表示的最小价值。
与前两题相比,关键是确定max的大小。
#include <stdio.h>
#include <string.h>
const int MAX=8000;
int main()
{
int z,max,c1[MAX+5],c2[MAX+5],num[4],money[4]={0,1,2,5};
while(scanf("%d%d%d",&num[1],&num[2],&num[3]),num[1]||num[2]||num[3])
{
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
c1[0]=1;
max=0;
for(int i=1;i<=3;i++)
{
max += money[i]*num[i];
for(int j=0;j<=max;j++)
{
for(int k=0;k<=num[i] && j+k*money[i]<=max;k++)
{
c2[j+k*money[i]] += c1[j];
}
}
memcpy(c1,c2,sizeof(c2));
memset(c2,0,sizeof(c2));
}
for(int i=1;;i++)
{
if(!c1[i])
{
printf("%d\n",i);
break;
}
}
}
return 0;
}
当然,此题用母函数并不是最好解法。最好解法如下,
稍加分析可知,面值大的不能表示面值小的,所以我们要先考虑面值小的硬币。
如果1-4分可以全部被表示,那么它可以表示当前硬币的所有组合。那么结果就应该是所有硬币价值总和加一。
如果1-4分不可以全部被表示,那么它所不能表示的最小价值就应该是这1-4分中不可以被表示的最小价值。
代码如下。
#include <stdio.h>
int main()
{
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c),a||b||c)
{
if(a==0)
printf("1\n");
else if(a+2*b<4)
printf("%d\n",a+2*b+1);
else
printf("%d\n",a+2*b+5*c+1);
}
return 0;
}
分享到:
相关推荐
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
教程来自HDU 的ACM教案,非常好的一个资料
教程来自HDU 的ACM教案,非常好的一个资料
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
ACM题库,一些题目和答案,以及解题报告,传上来共享
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU 里面的2000~2099道题目的源码。谢谢支持
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
杭电OnlineJudge 200-2099的解题报告
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码