【回溯】邮票问题
题目描述
设有已知面额的邮票m种,每种有n张。问:用总数不超过n张的邮票进行组合,能组合的邮票中可以连续出现面额数最多有多少(1<=m<=100,1<=n<=100,1<=邮票面额<=255)
输入
第一行:n和m的值,中间有一空格隔开
第二行:m种邮票的面额,每个数中间用一空格隔开。
第二行:m种邮票的面额,每个数中间用一空格隔开。
输出
连续面额数的最大值
样例输入
4 3
1 2 4
样例输出
14
用price数组记录所组成金额的最小张数
用已求的(1 - n-1)的price求price【n】
price[n] = min(price[n - a[i]])
#include<cstdio> #include <iostream> #include<cstdlib> #include <algorithm> using namespace std; long long int h[17]; const int MAXN = 25600; int price[MAXN], a[101]; int main(){ int N, M; scanf("%d%d", &M, &N); for(int i = 0; i < N; i++) scanf("%d", &a[i]); sort(a, a+N); int cnt = 1; price[0] = 0; while(true){ int ans = MAXN; for(int i = 0; i < N; i++){ if(a[i] > cnt){ break; } ans = min(price[cnt - a[i]]+1, ans); } if(ans > M) { printf("%d ", cnt-1); break; } price[cnt++] = ans; // printf("%d %d ", cnt - 1, ans); } return 0; }