(Educational Codeforces Round 9)Thief in a Shop(dp)

Thief in a Shop
time limit per test5 seconds memory limit per test512 megabytes inputstandard input outputstandard output A thief made his way to a shop.
As usual he has his lucky knapsack with him. The knapsack can contain k objects. There are n kinds of products in the shop and an infinite number of products of each kind. The cost of one product of kind i is ai.
The thief is greedy, so he will take exactly k products (it’s possible for some kinds to take several products of that kind).
Find all the possible total costs of products the thief can nick into his knapsack.
Input
The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of products the thief will take.
The second line contains n integers ai (1 ≤ ai ≤ 1000) — the costs of products for kinds from 1 to n.
Output
Print the only line with all the possible total costs of stolen products, separated by a space. The numbers should be printed in the ascending order.
Examples
input
3 2 1 2 3
output
2 3 4 5 6
input
5 5 1 1 1 1 1
output
5
input
3 3 3 5 11
output
9 11 13 15 17 19 21 25 27 33
문제의 뜻은 n개수이다. 그리고 이 n개수 중에서 k개를 골라 더하면 모두 몇 가지를 더할 수 있느냐고 묻는다.
문제풀이: 다항식 덧셈, k회 덧셈, 마지막 수가 무엇인지 물어보세요.DP.pp[i]는 최소한 몇 개의 비a[1]를 사용하면 a[1]*k+i를 구성할 수 있음을 나타낸다.

#include<bits/stdc++.h>
using namespace std;

int a[1010], dp[1000005], done[1010]={0};

int main()
{
    int mod = 1e9;
    fill( dp + 1, dp + 1000001 , mod);
    int n ,k, mn = mod, mx = 0;
    cin >> n >> k;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i];
        mn = min( mn , a[i]);
        mx = max( mx , a[i]);
    }
    for(int i=1;i<=n;++i)
        a[i] -= mn;

    int t = 0;
    for(int i=1;i<=n;++i)
        if( a[i] != 0)
            a[++t] = a[i];          

    n = t;
    dp[0]=0;
    for(int i = 1; i <= n;++i){
        if( done[a[i]])
            continue;
        done[a[i]] = 1;
        for(int j = 1; j<=mx*k;++j){
            if(j>=a[i])
                if(dp[j] > dp[j-a[i]] + 1)
                    dp[j] = dp[j-a[i]] + 1;
        }
    }


    for(int i = 0; i <= mx * k; ++i)
        if( dp[i] <= k)
            printf("%d ",mn * k + i);

    return 0;
}