uva165 - stamps(邮票）

本文主要是介绍uva165 - stamps(邮票），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不得不说这道题，对我来说很难，开始的时候甚至连题意都弄不清，

看了人家的代码，看懂了第一种方法，第一种方法很好理解，但是比较耗时。因为它没次递归都得算出那些值有可能出现。就是每次递归中都得包含调用递归。

代码如下：

#include <cstdio>
#include <cstring>
int stamp[10], maxstamp[10], ans[10], max, h, k;
void is_visit(int n, int cur, int sum, int *vis)
{if(cur==h) return;for(int i = 0; i < n; i++) {vis[sum+stamp[i]] = 1;is_visit(n,cur+1,sum+stamp[i],vis);}
}
void print_value(int cur)
{if(k==cur){int t = maxstamp[cur-1];if(max<t){max = t;for(int i = 0; i < cur; i++) ans[i] = stamp[i];}return;}int vis[200], j;for(int i = stamp[cur-1]+1; i<=maxstamp[cur-1]+1; i++){memset(vis,0,sizeof(vis));stamp[cur] = i;is_visit(cur+1,0,0,vis);j = 0;while(vis[++j]);maxstamp[cur] = j-1;print_value(cur+1);}
}
int main ()
{while(scanf("%d%d",&h,&k)&&h+k){max = 0;stamp[0] = 1; maxstamp[0] = h;print_value(1);for(int i = 0; i < k; i++)printf("%3d",ans[i]);printf(" ->%3d\n",max);}return 0;
}

第二种方法，听说是用的动归，还没学到，所以我不知道它是怎么动归的，但是我看懂了它的意思。

就是没添加一个面值，就寻找是否存在用该面值以更少的张数来凑够某一个值。若存在，则记录下此时的最少张数。

详解请浏览：http://blog.csdn.net/shankeliupo/article/details/8606712点击打开链接

代码如下：

#include <cstdio>
#include <cstring>
#define INF 2147483647
#define MAX 2000
int max, h, k, stamp[10], maxstamp[10], ans[10], minnum[MAX];
void print_ans(int cur)
{if(cur==k){int t = maxstamp[cur-1];if(max<t){max = t;for(int i = 0; i < k; i++) ans[i] = stamp[i];}return ;}int temp[MAX];memcpy(temp,minnum,sizeof(minnum));for(int i = stamp[cur-1]+1; i <= maxstamp[cur-1]+1; i++){stamp[cur] = i;for(int j = 0; j < stamp[cur-1]*h; j++) if(minnum[j]<h)for(int num = 1; num <= h - minnum[j]; num++) if(minnum[j]+num<minnum[j+i*num]&&j+i*num<MAX)minnum[j+i*num] = minnum[j]+num;int j = maxstamp[cur-1];while(minnum[++j]<INF);maxstamp[cur] = j-1;print_ans(cur+1);memcpy(minnum,temp,sizeof(temp));}
}
int main ()
{while(scanf("%d%d",&h,&k)&&h+k){stamp[0] = 1; maxstamp[0] = h; max = -1;for(int i = 0; i <= h; i++) minnum[i] = i;for(int i = h+1; i < MAX; i++) minnum[i] = INF;print_ans(1);for(int i = 0; i < k; i++) printf("%3d",ans[i]);printf(" ->%3d\n", max);}return 0;
}

这篇关于uva165 - stamps(邮票）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---