题解 | Stamps

这道题洛谷都标的黄题，

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int dp[100000005];  //记录凑到 i 的最少票数
int main(){
    int k, n;
    cin >> k >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int maxn = a[n] * k;
    fill(dp, dp + maxn + 1, INT_MAX);

    dp[0] = 0;  //面值为0 无法拼凑
    for(int i = 1; i <= maxn; i++)  //直接遍历一遍
        for(int j = 1; j <= n; j++){  //枚举邮票面值
            if(a[j] > i) break;  //如果邮票 > 要拼凑面值 ： 无法拼凑
            if(dp[i - a[j]] != INT_MAX)  
                //如果 i - a[j] 的面值可以拼凑，这个面值也可以拼凑， dp[i - a[j]] + 1
                dp[i] = min(dp[i], dp[i - a[j]] + 1); //取最小拼凑张数
        }
    int cnt = 0;
    for(int i = 1; i <= maxn; i++){
        if(dp[i] != INT_MAX && dp[i] <= k)  //判断， 可以取到， 张数 <= k
            cnt++;
        else  //如果中断，直接跳出循环
            break;
    }
    cout << cnt << endl;
    
    return 0;
}