Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1140208
  • 博文数量: 196
  • 博客积分: 4141
  • 博客等级: 中将
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-21 20:04
文章存档

2019年(31)

2016年(1)

2014年(16)

2011年(8)

2010年(25)

2009年(115)

分类:

2009-06-21 12:47:14

连续邮资问题

Time Limit:1sMemory limit:32M
Accepted Submit:88Total Submit:220

G国发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,使得可在1张 信封上贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续 邮资区间是1到70。 编程任务: 对于给定的正整数m和n,计算出邮票面值的最佳设计。

数据输入:
输入数据每一行给出2个正整数m和n的值(1<=n,m<=9),最后以0 0 表示文件结束。

结果输出:
对于输入中每一行的正整数m和n,将最大连续邮资区间输出。

样例输入

4 5
0 0

样例输出

70

#include<stdio.h>
#include<string.h>

#define MAX_VAL(x, y) (((x) > (y)) ? (x) : (y))
#define MIN_VAL(x, y) (((x) < (y)) ? (x) : (y))

int n, m;
int coins[20];
int letter[10000];
int r;

int check(int num)
{
    int i;
    int v;
    int maxv;
    
    maxv = coins[num];
    while (1)
    {
        v = 1000;
        for (i = 1; i <= num; ++i)
        {
            if (maxv - coins[i] < 0)
                continue;
            v = MIN_VAL(v, letter[maxv - coins[i]]);
        }
        if (v >= m)
            break;
        letter[maxv] = v + 1;
        ++maxv;
    }

    return maxv - 1;
}

int search(int num, int maxv)
{
    int i, r;
    int val;

    if (num >= n)
        return maxv;

    val = 0;
    for (i = maxv + 1; i >= coins[num] + 1; --i)
    {
        //if (num + 1 == n && i * m <= val)

            //continue;

        coins[num + 1] = i;
        r = check(num + 1);
        r = search(num + 1, r);
        val = MAX_VAL(r, val);
    }

    return val;
}

int main()
{
    int val;
    int i;

    while (scanf("%d %d", &m, &n) && m)
    {
        coins[1] = 1;
        for (i = 0; i <= m; ++i)
            letter[i] = i;
        val = search(1, m);
        printf("%d\n", val);
    }
    
    return 0;
}

阅读(1819) | 评论(0) | 转发(0) |
0

上一篇:Edit Ladders

下一篇:Binary Search Tree II

给主人留下些什么吧!~~