洛谷P1021 [NOIP1999 提高组] 邮票面值设计题解

题目链接：P1021 [NOIP1999 提高组] 邮票面值设计

题意：

给定一个信封，最多只允许粘贴 \(N\) 张邮票，计算在给定 \(K(N+K \le 15)\) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 \(\mathrm{MAX}\)，使在 \(1\) 至 \(\mathrm{MAX}\) 之间的每一个邮资值都能得到。

例如，\(N=3\)，\(K=2\)，如果面值分别为 \(1\) 分、\(4\) 分，则在 \(1\sim 6\) 分之间的每一个邮资值都能得到（当然还有 \(8\) 分、\(9\) 分和 \(12\) 分）；如果面值分别为 \(1\) 分、\(3\) 分，则在 \(1\sim 7\) 分之间的每一个邮资值都能得到。可以验证当 \(N=3\)，\(K=2\) 时，\(7\) 分就是可以得到的连续的邮资最大值，所以 \(\mathrm{MAX}=7\)，面值分别为 \(1\) 分、\(3\) 分。

输入格式：

\(2\) 个整数，代表 \(N\)，\(K\)。

输出格式：

输出共 \(2\) 行。

第一行输出若干个数字，表示选择的面值，从小到大排序。

第二行，输出 MAX=S，\(S\) 表示最大的面值。

本题的正解复杂度是错误的，不过我们还是来讲讲怎么做。

显然是暴搜。考虑暴力枚举 \(k\) 个面值，然后用 dp 来检验。

时间复杂度 \(\mathcal{O}(n^{k\operatorname{\uparrow\uparrow} 2})\) ，也就是 \(\mathcal{O}(n^{k^k})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(20))
#define M ((int)(1e6 + 15))

int n,k,res,val[N],ans[N],vis[M];
void check()
{
    const int Max = val[k] * n; 
    for(int i = 1; i <= Max; i++) vis[i] = INF;
    for(int i = 1; i <= k; i++) vis[val[i]] = 1;
    for(int sum = 1; sum <= Max; sum++)
    {
        if(vis[sum] == 1) continue;
        for(int i = 1; i <= k; i++)
        {
            if(sum < val[i]) break;
            down(vis[sum], vis[sum - val[i]] + 1);
        }
        if(vis[sum] > n)
        {
            if(--sum > res)
            {
                res = sum;
                memcpy(ans, val, (k + 1) * sizeof(int));
            }
            return ;
        }
    }
    if(Max > res)
    {
        res = Max;
        memcpy(ans, val, (k + 1) * sizeof(int));
    }
}
void dfs(int x)
{
    if(x == k + 1) return check();
    for(int i = val[x - 1] + 1; i <= val[x - 1] * n + 1; i++) {
        val[x] = i; dfs(x + 1);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; dfs(1);
    for(int i = 1; i <= k; i++) {
        cout << ans[i] << " \n"[i == k];
    }
    cout << "MAX=" << res << '\n';
    return 0;
}

打表代码：（然而这垃圾题数据水的一匹）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(20))
#define M ((int)(1e6 + 15))

int n,k,res,val[N],ans[N],vis[M];
void check()
{
    const int Max = val[k] * n; if(Max <= res) return;
    for(int i = 1; i <= Max; i++) vis[i] = INF;
    for(int i = 1; i <= k; i++) vis[val[i]] = 1;
    for(int sum = 1; sum <= Max; sum++)
    {
        if(vis[sum] == 1) continue;
        for(int i = 1; i <= k; i++)
        {
            if(sum < val[i]) break;
            down(vis[sum], vis[sum - val[i]] + 1);
        }
        if(vis[sum] > n)
        {
            if(--sum > res)
            {
                res = sum;
                memcpy(ans, val, (k + 1) * sizeof(int));
            }
            return ;
        }
    }
    if(Max > res)
    {
        res = Max;
        memcpy(ans, val, (k + 1) * sizeof(int));
    }
}
void dfs(int x)
{
    if(x == k + 1) return check();
    for(int i = val[x - 1] + 1; i <= val[x - 1] * n + 1; i++) {
        val[x] = i; dfs(x + 1);
    }
}
void clear() { res = 0; memset(ans, 0, sizeof(ans)); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    freopen("check.out","w",stdout);
    const int MaxL = 10;
    cout << "string ans[20][20] = {\n";
    for(n = 0; n <= MaxL; n++)
    {
        cout << "    { ";
        for(k = 0; n + k <= MaxL; k++)
        {
            clear(); cerr << "n = " << n << ", " << "k = " << k << '\n';
            if(k != 0) cout << ' '; cout << "\""; dfs(1);
            for(int i = 1; i <= k; i++) {
                cout << ans[i]; cout << ((i != k) ? " " : "\\n");
            }
            cout << "MAX=" << res << "\\n";
            cout << "\""; if(n + k != MaxL) cout << ',';
        }
        cout << " },\n";
    }
    cout << "};";
    return 0;
}