首页 > 搜索 > DFS搜索 > HDU 1641 Stamps-DFS-[解题报告] C++
2013
12-21

HDU 1641 Stamps-DFS-[解题报告] C++

Stamps

问题描述 :

The government of Nova Mareterrania requires that various legal documents have stamps attached to them so that the government can derive revenue from them. In terms of recent legislation, each class of document is limited in the number of stamps that may be attached to it. The government wishes to know how many different stamps, and of what values, they need to print to allow the widest choice of values to be made up under these conditions. Stamps are always valued in units of $1.

This has been analysed by government mathematicians who have derived a formula for n(h,k), where h is the number of stamps that may be attached to a document, k is the number of denominations of stamps available, and n is the largest attainable value in a continuous sequence starting from $1. For instance, if h=3, k=2 and the denominations are $1 and $4, we can make all the values from $1 to $6 (as well as $8, $9 and $12). However with the same values of h and k, but using $1 and $3 stamps we can make all the values from $1 to $7 (as well as $9). This is maximal, so n(3,2) = 7.

Unfortunately the formula relating n(h,k) to h, k and the values of the stamps has been lost–it was published in one of the government reports but no-one can remember which one, and of the three researchers who started to search for the formula, two died of boredom and the third took a job as a lighthouse keeper because it provided more social stimulation.

The task has now been passed on to you. You doubt the existence of a formula in the first place so you decide to write a program that, for given values of h and k, will determine an optimum set of stamps and the value of n(h,k).

输入:

Input will consist of several lines, each containing a value for h and k. The file will be terminated by two zeroes (0 0). For technical reasons the sum of h and k is limited to 9. (The President lost his little finger in a shooting accident and cannot count past 9).

输出:

Output will consist of a line for each value of h and k consisting of the k stamp values in ascending order right justified in fields 3 characters wide, followed by a space and an arrow (->) and the value of n(h,k) right justified in a field 3 characters wide.

样例输入:

3 2
0 0

样例输出:

  1  3 ->  7

 Stamps 


The government of Nova Mareterrania requires that various legal documents have stamps attached to them so that the government can derive revenue from them. In terms of recent legislation, each class of document is limited in the number of stamps that may be
attached to it. The government wishes to know how many different stamps, and of what values, they need to print to allow the widest choice of values to be made up under these conditions. Stamps are always valued in units of $1.

This has been analysed by government mathematicians who have derived a formula for n(h,k), where h is the number of stamps that may be attached to a document, k is the number of denominations of stamps available,
and n is the largest attainable value in a continuous sequence starting from $1. For instance, if h=3, k=2 and the denominations are $1 and $4, we can make all the values from $1 to $6 (as well as $8, $9 and $12). However with the
same values of h and k, but using $1 and $3 stamps we can make all the values from $1 to $7 (as well as $9). This is maximal, so n(3,2) = 7.

Unfortunately the formula relating n(h,k) to hk and the values of the stamps has been lost–it was published in one of the government reports but no-one can remember which one, and of the three researchers who
started to search for the formula, two died of boredom and the third took a job as a lighthouse keeper because it provided more social stimulation.

The task has now been passed on to you. You doubt the existence of a formula in the first place so you decide to write a program that, for given values of h and k, will determine an optimum set of stamps and the value of n(h,k).

Input

Input will consist of several lines, each containing a value for h and k. The file will be terminated by two zeroes (0 0). For technical reasons the sum of h and k is limited to 9. (The President lost his little finger in
a shooting accident and cannot count past 9).

Output

Output will consist of a line for each value of h and k consisting of the k stamp values in ascending order right justified in fields 3 characters wide, followed by a space and an arrow (->) and the value of n(h,k)
right justified in a field 3 characters wide.

Sample input

3 2
0 0

Sample output

  1  3 ->  7

题目大意:给出邮票数量h,和邮票面值种类k,要求你选出k种面值的邮票,通过这些1 ~ h张邮票所组成的面值数连续最大。

比如:选择1 和 2,(在h= 3时)可以组成的面值数有1、2、3、4、5、6,所以此时最大连续面额就为6

但如果选择1 和3 的话,可组成的面值数就有1、2、3、4、5、6、7、  9,注意,没有8,所以最大连续面额为7.

解题思路:将所有面额情况枚举出来比较就好了,但是这是后就碰到了面值枚举的上限问题,其实仔细想一下不难发现,当前第i个面值的最大值其实就是前面0 ~ i能组成最大面值再加1,再大的话就不能形成连续的也就不符合题意了。

#include <stdio.h>
#include <string.h>
#define N 200

int h, k, Max,maxvalue[N];
int nowvalue[N], recvalue[N];
bool vis[N];
void count(int n,int cur, int sum){
    vis[sum] = true;
    if (n >= h)
	return ;
    for (int i = 0; i <= cur; i++)
	count(n + 1, cur, sum + nowvalue[i]);
}

void find(int cur){
    if (cur >= k){
	if (maxvalue[cur - 1] > Max){
	    Max = maxvalue[cur - 1];
	    memcpy(recvalue, nowvalue, sizeof(nowvalue));
	}
	return;
    }
    for (int i = nowvalue[cur - 1]; i <= maxvalue[cur - 1] + 1; i++){
	memset(vis, 0, sizeof(vis));
	nowvalue[cur] = i;
	count(0, cur, 0);

	int t = 1, num = 0;
	while(vis[t++])num++;

	maxvalue[cur] = num;
	find(cur + 1);	
    }
}

int main(){
    while (scanf("%d%d", &h, &k), h && k){
	// Init.
	memset(vis, 0, sizeof(vis));
	memset(maxvalue, 0, sizeof(maxvalue));
	memset(nowvalue, 0, sizeof(nowvalue));
	memset(recvalue, 0, sizeof(recvalue));

	maxvalue[0] = h;
	nowvalue[0] = 1;
	Max = 0;
	find(1);

	for (int i = 0; i < k; i++)
	    printf("%3d", recvalue[i]);
	printf(" ->%3d\n", Max);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/keshuai19940722/article/details/9751839


,
  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法