uva 165 Stamps

题意：

　　现有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]。

代码：

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 1024

 #define MAXM 100

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {printf("%d\n", x);}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 int h, k;

 int n, ans;

 int x[MAXM], y[MAXN];

 int f[MAXM];

 void init()

 {

     memset(x, , sizeof(x));

     memset(y, 0x3f, sizeof(y));

     memset(f, , sizeof(f));

     x[] = ;

     n = h;

     ans = ;

     for(int i = ; i <= n; i ++)

         y[i] = i;

 }

 void dfs(int pos)

 {

     if(pos >= k)

     {

         if(n > ans)

         {

             ans = n;

             for(int i = ; i < k; i ++)

                 f[i] = x[i];

         }

         return ;

     }

     int temp[MAXN];

     int temp_ans = n;

     for(int i = ; i < MAXN; i ++) temp[i] = y[i];

     for(int val = x[pos - ] + ; val <= n + ; val ++)

     {

         x[pos] = val;

         for(int ww = ; ww < x[pos - ] * h; ww ++)

         {

             if(y[ww] >= h) continue;

             for(int num = ; num <= h - y[ww]; num ++)

                 if(y[ww] + num < y[ww + num * val] && (ww + num * val < MAXN))

                     y[ww + num * val] = y[ww] + num;

         }

         while(y[n + ] < INF) n ++;

         dfs(pos + );

         n = temp_ans;

         for(int i = ; i < MAXN; i ++) y[i] = temp[i];

     }

 }

 void solve()

 {

     init();

     dfs();

     for(int i = ; i < k; i ++)

         printf("%3d", f[i]);

     printf(" ->%3d\n", ans);

 }

 int main()

 {

     while(scanf("%d %d", &h, &k) && (h + k))

     {

         solve();

     }

     return ;

 }

巴特西

uva 165 Stamps

最新文章

热门文章