CodeForces632E 神奇的多重背包

时间：2023-03-09 13:41:56
CodeForces632E 神奇的多重背包

https://cn.vjudge.net/problem/333897/origin

万万没想到这题表面上是个多重背包，实际上确实是个多重背包

题意 n种物品每种物品有无限个，每个物品有一个价格，现在问选取k个的所有可能总价。

第一眼觉得是一个多重背包，但是问题在于限制一定要选取K个的条件，显然不是那么容易的

如果我们把dp[1000 * 1000]表示为这个数字至少多少个数字加起来或者至多多少个数字加起来取得也是有问题的，因为无论这个数字大于K或者小于K都是有概率取不到的，不满足单调性。

这里有一个奥妙重重的方法。

因为最终答案的区间一定是在min-x * K到max-x * K之间的，我们可以考虑先对每一个数字减去min_x,这时候就满足了如果这个数字可以通过小于K的物品取到，就一定可以通过等于K的物品取到，因为缺的可以通过价值为0的minx来补上，满足了单调性之后就可以直接DP了

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,tmp,K;

int a[maxn];

int dp[maxn * maxn];

int main()

{

    Sca2(N,K);

    For(i,,N) Sca(a[i]);

    sort(a + ,a +  + N);

    N = unique(a + ,a +  + N) - a - ;

    For(i,,N) a[i] -= a[];

    Mem(dp,0x3f);

    dp[] = ;

    For(i,,N){

        int t = a[i] * K;

        For(j,a[i],t){

            dp[j] = min(dp[j],dp[j - a[i]] + );

        }

    }

    int sum = a[N] * K;

    int base = a[] * K;

    For(i,,sum){

        if(dp[i] <= K){

            printf("%d ",i + base);

        }

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章