主要思路

这道题所有购买方案的取值上界为\(a_i \times k\)，差不多就是\(1e5\)级别。考虑超级大暴力，设置状态\(f[i][j][w]\)为选了\(i\)个次、最后一次是第\(j\)种硬币且当前总价为\(w\)是否可行。这个转移算上取值上限就差不多是\(O(n^4)\)的，只能过掉一部分分数。

考虑进行状态转化。我们先让所有商品的价格减去价格最小值，然后剩下购买的方案就变成了形如\(k*minVal + sum\)的形式，然后我们设置状态\(f[i][j]\)最后一次选第\(i\)种商品，且选到\(j\)的最少选择次数，统计次数小于\(k\)的状态就可以了。

代码

// FOJ4681.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 550;

int n, k, dp[MAX_N * MAX_N], ai[MAX_N], mx_range, mi;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    sort(ai + 1, ai + 1 + n);
    mi = ai[1];
    for (int i = 1; i <= n; i++)
        ai[i] -= mi;
    mx_range = ai[n];
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ai[i] == ai[i - 1])
            continue;
        for (int j = 1; j <= k * mx_range; j++)
            if (j >= ai[i])
                dp[j] = min(dp[j], dp[j - ai[i]] + 1);
    }
    for (int i = 0; i <= mx_range * k; i++)
        if (dp[i] <= k)
            printf("%d ", i + mi * k);
    return 0;
}