本文主要是介绍165-Stamps【回溯】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
回溯
给h和k的意思是在k种邮票中选h个邮票
基本的连续邮资问题
| 15226160 | 165 | Stamps | Accepted | C++ | 0.062 | 2015-03-27 07:21:37 |
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 222;
const int maxd = 15;
int h,k;
int vis[maxn];
int array[maxd];
int ans_value;
int ans_array[maxd];
void dfs(int step,int arr[],int size,int sum){vis[sum] = 1;if(step == h){return;}for(int i = 0; i < size; i++)dfs(step + 1,arr,size,sum + arr[i]);
}
void dfs2(int step,int pos,int arr[]){dfs(0,arr,step,0);int next;for(int i = 1; ; i++)if(!vis[i]){next = i;break;}if(step == k){if(next - 1 > ans_value){for(int i = 0; i < step; i++)ans_array[i] = arr[i];ans_value = next - 1;}return;}int vis_temp[maxn];memcpy(vis_temp,vis,sizeof(vis));for(int i = pos; i <= next; i++){arr[step] = i;dfs2(step + 1,i + 1,arr);memcpy(vis,vis_temp,sizeof(vis_temp));}
}
int main(){while(scanf("%d%d",&h,&k) && h){memset(vis,0,sizeof(vis));array[0] = 1;ans_value = 0;dfs2(1,2,array);for(int i = 0; i < k; i++)printf("%3d",ans_array[i]);printf(" ->%3d\n",ans_value);}return 0;
}
这篇关于165-Stamps【回溯】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
