题目描述 Description

给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。

输入描述 Input Description

N和K

输出描述 Output Description

每种邮票的面值，连续最大能到的面值数。数据保证答案唯一。

样例输入 Sample Input

3 2

样例输出 Sample Output

1 3
MAX=7

题解：

这道题一看数据范围就知道是可以搜索的，但是不可能搜索枚举每种方案，这样一定会T；
对于求最大值，我们可以用DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, k, maxn;
int ans[23333], dp[2333], a[2333];
inline int deal(int x)
{
    if (!x)
        return 0;
    memset(dp, 0x7f, sizeof(dp));
    dp[0] = 0;
    int i = 1;
    do
    {
        for (int j = 1; j <= x && a[j] <= i; j++)
            dp[i] = min(dp[i - a[j]] + 1, dp[i]);
    }while(dp[i++] <= n);
    return i - 2;
}
inline void dfs(int x)
{
    if (x >= k)
    {
        int ls = deal(k);
        if (ls <= maxn)
            return;
        for (int i = 1; i <= k; i++)
            ans[i] = a[i];
        maxn = ls;
        return ;
    }
    else
    {
        int ls = deal(x);
        for (int i = ls + 1; i > a[x]; i--)
        {
            a[x+1] = i;
            dfs(x+1);
        }
    }
}
int main()
{
    cin >> n >> k;
    dfs(0);
    for (int i = 1; i <= k; i++)
        cout << ans[i] << " ";
    puts("");
    cout <<"MAX="<<maxn;
    return 0;
}