题解 | 最小邮票数

#include<bits/stdc++.h>
#define int long long
#define _for(i, a, b) for(int i = a;i < b;++i)
#define _rep(i, a, b) for(int i = a;i <= b;++i)
int readll(){int x; scanf("%lld", &x); return x;}
using namespace std; 
const int maxn = 20 + 5;
#define INF 0x3f3f3f3f
bool flag[maxn];
int _min, M, _count;
void dfs(int a[], int n, int cost){
	if(cost > M)	return;
	if(cost == M){
		_min = min(_min, _count);
		return;
	}
	for(int i = n - 1;i >= 0;--i){
		if(cost + a[i] * (i + 1) < M)	break;
		if(flag[i])	continue;
		cost += a[i];
		flag[i] = true;
		++_count;
		dfs(a, n, cost);
		cost -= a[i];
		flag[i] = false;
		--_count;
	}
}

signed main(){
	
	while(scanf("%lld", &M) == 1){
		memset(flag, false, sizeof(flag));
		_min = INF; _count = 0;
		int N;
		N = readll();
		int * a = new int[N];
		_for(i, 0, N)	a[i] = readll();
		dfs(a, N, 0);
		if(_min != INF)	printf("%lld\n", _min);
		else	printf("0\n");
	} 
	return 0;
}

dfs加剪纸解决