首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >uva 165 Stamps

uva 165 Stamps

作者头像
若羽
发布2019-07-15 16:47:41
5020
发布2019-07-15 16:47:41
举报
文章被收录于专栏:Code思维奇妙屋Code思维奇妙屋

题意:

  现有k种邮票面额, 一封信上最多贴h张邮票。

  求能贴出的最大连续区间,即[1, max_value]这个区间内的所有面额都能贴出来。

  并输出k种面额, h + k <= 9.

思路:

  这是一个经典的数学问题:连续邮资问题。

  1)面额为1的邮票肯定要选进去(不然连1都贴不出来, 还怎么连续)。

    此时最大连续区间为 [1, h]

  2)当 [1,i - 1], 前i - 1种邮票面额确定后, 第i种邮票面额的取值区间为:[x[i - 1] + 1, max_value + 1], x[]数组存放邮票面额。

    枚举第i种邮票面额, 并更新[1, max_value]。

代码:

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <ctime>
  6 #include <set>
  7 #include <map>
  8 #include <list>
  9 #include <stack>
 10 #include <queue>
 11 #include <string>
 12 #include <vector>
 13 #include <fstream>
 14 #include <iterator>
 15 #include <iostream>
 16 #include <algorithm>
 17 using namespace std;
 18 #define LL long long
 19 #define INF 0x3f3f3f3f
 20 #define MOD 1000000007
 21 #define eps 1e-6
 22 #define MAXN 1024
 23 #define MAXM 100
 24 #define dd {cout<<"debug"<<endl;}
 25 #define pa {system("pause");}
 26 #define p(x) {printf("%d\n", x);}
 27 #define pd(x) {printf("%.7lf\n", x);}
 28 #define k(x) {printf("Case %d: ", ++x);}
 29 #define s(x) {scanf("%d", &x);}
 30 #define sd(x) {scanf("%lf", &x);}
 31 #define mes(x, d) {memset(x, d, sizeof(x));}
 32 #define do(i, x) for(i = 0; i < x; i ++)
 33 #define dod(i, x, l) for(i = x; i >= l; i --)
 34 #define doe(i, x) for(i = 1; i <= x; i ++)
 35 int h, k;
 36 int n, ans;
 37 int x[MAXM], y[MAXN];
 38 int f[MAXM];
 39 void init()
 40 {
 41     memset(x, 0, sizeof(x));
 42     memset(y, 0x3f, sizeof(y));
 43     memset(f, 0, sizeof(f));
 44 
 45     x[0] = 1;
 46     n = h;
 47     ans = 0;
 48     for(int i = 0; i <= n; i ++)
 49         y[i] = i;
 50 }
 51 void dfs(int pos)
 52 {
 53     if(pos >= k)
 54     {
 55         if(n > ans)
 56         {
 57             ans = n;
 58             for(int i = 0; i < k; i ++)
 59                 f[i] = x[i];
 60         }
 61         return ;
 62     }
 63 
 64     int temp[MAXN];
 65     int temp_ans = n;
 66     for(int i = 0; i < MAXN; i ++) temp[i] = y[i];
 67 
 68     for(int val = x[pos - 1] + 1; val <= n + 1; val ++)
 69     {
 70         x[pos] = val;
 71         for(int ww = 0; ww < x[pos - 1] * h; ww ++)
 72         {
 73             if(y[ww] >= h) continue;
 74             for(int num = 1; num <= h - y[ww]; num ++)
 75                 if(y[ww] + num < y[ww + num * val] && (ww + num * val < MAXN))
 76                     y[ww + num * val] = y[ww] + num;
 77         }
 78 
 79         while(y[n + 1] < INF) n ++;
 80 
 81         dfs(pos + 1);
 82 
 83         n = temp_ans;
 84         for(int i = 0; i < MAXN; i ++) y[i] = temp[i];
 85     }
 86 }
 87 
 88 void solve()
 89 {
 90     init();
 91     dfs(1);
 92     for(int i = 0; i < k; i ++)
 93         printf("%3d", f[i]);
 94     printf(" ->%3d\n", ans);
 95 }
 96 
 97 int main()
 98 {
 99     while(scanf("%d %d", &h, &k) && (h + k))
100     {
101         solve();
102     }
103     return 0;
104 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-10-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档