Thief in a Shop 【CodeForces - 632E】【背包】

題目連結

  給了N個物品，每個物品無限個，我們要的是求剛好我們拿了K個物品的時候，能組成哪幾種數？

  我們可以想個辦法去填充，那麼就需要有一個所謂的0狀态，然後假如不足K個的時候，就可以拿這個所謂的0狀态來填充了，是以，我們把所有的數排序，然後都減去了a[1]，最後求的時候再把它加回去就可以了。

  我們求每個狀态下的最少的物品需求，dp[i]表示的是現在都減去0狀态時候的達到i這個數時候的最少要求的物品數。

  那麼，我們最後假如得到dp[i]≤K的話，那麼這個數就一定我們需要的，此時的還原回去就是i + dp[i] * bic + (K - dp[i]) * bic，其中bic指的就是一開始我們都減去的a[1]。"dp[i] * bic"是因為我們要取的這dp[i]個數一開始都減去了a[1]，"(K - dp[i]) * a[0]"是因為我們還需要填充這麼多個0狀态才能取得i這個值。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
#define MP3(a, b, c) MP(MP(a, b), c)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e3 + 7;
int N, K, a[maxN], bic, dp[maxN * maxN], ans[maxN * maxN], tot;
int main()
{
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++) scanf("%d", &a[i]);
    sort(a + 1, a + N + 1);
    bic = a[1];
    for(int i=1; i<=N; i++) a[i] -= bic;
    memset(dp, INF, sizeof(dp));    dp[0] = 0;
    for(int i=1; i<=N; i++)
    {
        for(int j=a[i]; j<=K * a[i]; j++)
        {
            dp[j] = min(dp[j], dp[j - a[i]] + 1);
        }
    }
    for(int i=0; i<=K*a[N]; i++) if(dp[i] <= K) ans[++tot] = i + dp[i] * bic + (K - dp[i]) * bic;
    for(int i=1; i<=tot; i++) printf("%d%c", ans[i], i == tot ? '\n' : ' ');
    return 0;
}