uva 165 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

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。表示用h张邮票，面额数不超过k。最长连续能表示的值是多少。
例如h=3,k=2 可以取两个面额是1和2，1和2在使用3张邮票的情况下，能连续表示1,2,3,4,5,6
1<=h+k<=9

#include<bits/stdc++.h>
using namespace std;
const int maxn=200;
int h,k;//h张邮票 k面值数
int ans[maxn],maxStampVal,stampVal[maxn],maxVal[maxn];
bool mark[maxn];

void get_ans(int cur,int n,int sum)
{
    mark[sum]=true;
    if(cur>=h)
        return;
    for(int i=0;i<=n;i++)
        get_ans(cur+1,n,sum+stampVal[i]);
}

void find_amount(int cur)
{
    if(cur>=k)
    {
        if(maxVal[cur-1]>maxStampVal)
        {
            maxStampVal=maxVal[cur-1];
            memcpy(ans,stampVal,sizeof(stampVal));
        }
        return ;
    }
    for(int i=stampVal[cur-1]+1;i<=maxVal[cur-1]+1;i++)
    {
        memset(mark,0,sizeof(mark));
        stampVal[cur]=i;
        get_ans(0,cur,0);
        int num=0,j=1;
        while(mark[j++])
            num++;
        maxVal[cur]=num;
        find_amount(cur+1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>h>>k,h+k)
    {
        stampVal[0]=1;
        maxVal[0]=h;
        maxStampVal=INT_MIN;
        find_amount(1);

        for(int i=0;i<k;i++)
            cout<<setw(3)<<ans[i];
        cout<<" ->"<<setw(3)<<maxStampVal<<endl;
    }
    return 0;
}

解法：

一开始题读错了，以为可选的面额为1到9。结果上来枚举所有面额值，然后用背包解的，当然，wa了。
后来看了这篇博客才知道这是一个经典的问题，连续邮资问题。
简单的枚举思路比较简单

首先枚举面额值，然后根据枚举出来的面额值计算当前这些面额能组成的最大连续的数是多少。

在枚举一个新的面额值时，枚举范围是关键。这个范围是[当前拥有的最大面值+1，当前的邮票种类所能表示的最大连续值+1]。
举个例子，当前手里有的邮票为1和2，那么下一次需要枚举的邮票范围必须是在[3,7]小于3没有意义，因为有1和2了。使用1和2最大能获得的连续数为6，那么如果下一个面额大于7，则7这个数不会出现。

还有更优的解法，具体思路是使用类似状态压缩的动态规划的策略。设置一个数组S(i)表示使用1->i这些面额且使用不超过m个邮票的贴法的集合。那么当枚举第i+1个邮票时，能获得的新的邮票的贴法就是把S(i)当中所有贴法小于m个的方法都加上第i+1个邮票的面额。得到的结果集合记为S(i+1)即可。 具体代码见上面的链接。