邮票问题详细题解【简单dp】

已知一个 N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限 K —— 表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资。

例如，假设有 1 分和 3 分的邮票；你最多可以贴 5 张邮票。很容易贴出 1 到 5 分的邮资（用 1 分邮票贴就行了），接下来的邮资也不难：

6 = 3 + 3 7 = 3 + 3 + 1 8 = 3 + 3 + 1 + 1 9 = 3 + 3 + 3 10 = 3 + 3 + 3 + 1 11 = 3 + 3 + 3 + 1 + 1 12 = 3 + 3 + 3 + 3 13 = 3 + 3 + 3 + 3 + 1

然而，使用 5 枚 1 分或者 3 分的邮票根本不可能贴出 14 分的邮资。因此，对于这两种邮票的集合和上限 K=5，答案是 M=13。

我们先给出将其看为多重集组合数来解得场景，不同之处在于，这里限制了邮票使用的最大数目。我们使用两个数组

d p [ i ] , c n t [ i ] dp[i],cnt[i] dp[i],cnt[i]表示使用最少 c n t [ i ] cnt[i] cnt[i]个邮票就能拼凑出大小为 i i i的邮资，那么动态规划的过程分为三步

不幸的是，多重集组合数经常面临着TLE的危险，上面也不例外，只能拿80分，看了大佬的题解之后发现自己是一个zz，其实只需要很简单得转换，我们就能拿下这道题，

注意看题，题目求得是从1开始得最长连续序列，因此我们只需要从i=0不断向上搜索，直到有一个i不能拼凑出来，就得到了最长连续序列

最重要的部分只有4行， d p [ i ] dp[i] dp[i]是我们拼凑出 i i i邮资使用的最少邮票数目，dp得过程其实就是不断更新最小邮票数目得过程，在满足数目要求 d p [ i ] < = K dp[i] while (cin >> K >> N) { memset(dp, 0, sizeof(dp)); ll maxx = 0; for (int i = 1; i > a[i]; sort(a + 1, a + N + 1);//一定要排序 int i = 0; while (dp[i]