uva 165

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

题意：在H张邮票，K种面值的情况下能确定的连续的最大邮票值是多少，第一种面值是1是一定的了，然后我们在已知面值的情况下能凑成的连续面值和范围，那么下一张我们能从这个范围里面选

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 200;int h,k;
int ans[MAXN],maxStampVal,stampVal[MAXN],maxVal[MAXN];
bool occur[MAXN];// cur当前用了几张票， n当前面额种数， sum面额之和 
void dfs(int cur,int n,int sum)  // 用n种面值能凑成的连续面值
{if (cur >= h){occur[sum] = true;return ;}occur[sum] = true ;for (int i = 0 ; i < n; i++)dfs(cur+1,n,sum+stampVal[i]);
}void search(int cur) // 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(occur,0,sizeof(occur));stampVal[cur] = i ;dfs(0,cur,0);int num = 0 ,j = 1;while (occur[j++])    // 肯定是能凑成连续的num++;maxVal[cur] = num ;search(cur+1);}
}int main()
{while (scanf("%d %d",&h,&k)!= EOF && h+k){stampVal[0] = 1;maxVal[0] = h ;maxStampVal = -34255556;search(1);for (int i = 0; i < k; i++)printf("%3d",ans[i]);printf(" ->%3d\n",maxStampVal);}return 0;
}

这篇关于uva 165的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---