专栏首页csxiaoyaoHDU 1085 母函数 硬币组合

HDU 1085 母函数 硬币组合

题目如下:

Holding Bin-Laden Captive!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13245    Accepted Submission(s): 5931

Problem Description

We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!  “Oh, God! How terrible! ”

Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up!  Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem? “Given some Chinese Coins (硬币) (three kinds-- 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.” You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!

Input

Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.

Output

Output the minimum positive value that one cannot pay with given coins, one line for one case.

Sample Input

1 1 3 0 0 0

Sample Output

4

先来一段暴力的做法:

#include<iostream>
using namespace std;
#define M 8000
void main()
{
	int a,b,c,x[M+10],i,j,k;
	while(cin>>a>>b>>c,a+b+c)
	{
		memset(x,0,sizeof(x));
		for(i=0;i<=c;i++)
			for(j=0;j<=b;j++)
				for(k=0;k<=a;k++)
					x[5*i+2*j+k]=1;
		i=0;
		while(++i)
			if(x[i]==0)
				break;
		cout<<i<<endl;
	}
}

这题目还可以尝试母函数的做法:

#include <iostream>
using namespace std;
int c1[10000], c2[10000];
int num[4];
int main()
{
    int nNum;
    while(scanf("%d %d %d", &num[1], &num[2], &num[3]) && (num[1]||num[2]||num[3]))
    {
        int _max = num[1]*1+num[2]*2+num[3]*5;
        for(int i=0; i<=_max; ++i)
        {
            c1[i] = 0;
            c2[i] = 0;
        }
        for(int i=0; i<=num[1]; ++i)
            c1[i] = 1;
        for(int i=0; i<=num[1]; ++i)
            for(int j=0; j<=num[2]*2; j+=2) 
                c2[j+i] += c1[i];
        for(int i=0; i<=num[2]*2+num[1]*1; ++i)
        {
            c1[i] = c2[i];
            c2[i] = 0;
        }
        for(int i=0; i<=num[1]*1+num[2]*2; ++i)
            for(int j=0; j<=num[3]*5; j+=5)
                c2[j+i] += c1[i];
        for(int i=0; i<=num[2]*2+num[1]*1+num[3]*5; ++i)
        {
            c1[i] = c2[i];
            c2[i] = 0;
        }
        int i;
 
        for(i=0; i<=_max; ++i)
            if(c1[i] == 0)
            {
                printf("%d\n", i);
                break;
            }
        if(i == _max+1)
            printf("%d\n", i);
    }
    return 0;
}

附母函数模板:

#include <iostream>
using namespace std;
const int _max = 10001; 
// c1是保存各项质量砝码可以组合的数目
// c2是中间量,保存每一次的情况
int c1[_max], c2[_max];   
int main()
{	 
	int nNum;
	int i, j, k;
	while(cin >> nNum)
	{
		for(i=0; i<=nNum; ++i)   // ---- ①
		{
			c1[i] = 1;
			c2[i] = 0;
		}
		for(i=2; i<=nNum; ++i)   // ----- ②
		{
			for(j=0; j<=nNum; ++j)   // ----- ③
				for(k=0; k+j<=nNum; k+=i)  // ---- ④
				{
					c2[j+k] += c1[j];
				}
			for(j=0; j<=nNum; ++j)     // ---- ⑤
			{
				c1[j] = c2[j];
				c2[j] = 0;
			}
		}
		cout << c1[n] << endl;
	}
	return 0;
}

我们来解释下上面标志的各个地方:

① 、首先对c1初始化,由第一个表达式(1+x+x2+..xn)初始化,把质量从0到n的所有砝码都初始化为1.

② 、 i从2到n遍历,这里i就是指第i个表达式,上面给出的第二种母函数关系式里,每一个括号括起来的就是一个表达式。

③、j 从0到n遍历,这里j就是只一个表达式里第j个变量,比如在第二个表达式里:(1+x2+x4....)里,第j个就是x2*j.

③ 、k表示的是第j个指数,所以k每次增i(因为第i个表达式的增量是i)。

④ 、把c2的值赋给c1,而把c2初始化为0,因为c2每次是从一个表达式中开始的

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 系统学习javaweb-01-java基础语法

    注意: Object类型的数组可以存储任意类型的数据 String[] arr = new String[1000];

    csxiaoyao
  • shell 常用快捷键

    csxiaoyao
  • LESS 学习demo

    csxiaoyao
  • 猜数字游戏的提示

    实现一个经典“猜数字”游戏。给定答案序列和用户猜的序列,统计有多少数字位置正确(A),有多少数字在两个序列都出现过但位置不对(B)。

    Vincent-yuan
  • 18级个人训练赛--2

    B --Consecutive Integers AtCoder 5037 思路:水题,签到~

    杨鹏伟
  • HDUOJ--2079选课时间(题目已修改,注意读题)

    选课时间(题目已修改,注意读题) Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/3...

    Gxjun
  • AGC015 D A or...or B Problem(智商题)

    设A,B二进制分解后第一个不同的位为i,那么显然i之前所有的数都是没用的(因为or出来的数都包含这些位)

    attack
  • 字母排序问题(c++实现)

    描述:编写一个程序,当输入不超过60个字符组成的英文文字时,计算机将这个句子中的字母按英文字典字母顺序重新排列,排列后的单词的长度要与原始句子中的长度 相同。例...

    用户2038589
  • 仿qq最新侧滑菜单

    为了后续对这个项目进行优化,比如透明度动画、背景图的位移动画,以及性能上的优化。 我把这个项目上传到github上面,请大家随时关注。 github地址 htt...

    xiangzhihong
  • 【USACO 2.4】Overfencing(bfs最短路)

    H行W列的迷宫,用2*H+1行的字符串表示,每行最多有2*W+1个字符,省略每行后面的空格。迷宫的边界上有且仅有两个出口,求每个点出发到出口的最短路。

    饶文津

扫码关注云+社区

领取腾讯云代金券