题目链接:http://codeforces.com/contest/632/problem/E
题意:http://blog.csdn.net/just_sort/article/details/54310734
解法2: DP
容易想到4维dp,用dp[i][j]表示取i次,价值为j是否存在,但是这样的复杂度为10^12爆了,所以要减少一维,先对n个数排序,然后n个数都减去第一个数(这样做的目的是恰好k次很难dp,n个数都减去最小的数后,第1个数就变为0,在这样的情况下,如果我们凑到价值为i的物品少于k件,如只用k-2件拼凑,那么另外两件可以看做都用第1个物品),然后用dp[i]表示最后取到价值为i的物品,dp就行了。
//CF 632E
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, k, a[maxn], dp[maxn*maxn]; //dp[i]表示最后取到价值为i的物品
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a+1, a+n+1);
int t = a[1];
for(int i = 1; i <= n; i++) a[i] -= t;
for(int i = 0; i <= 1000000; i++) dp[i] = 0x3f3f3f3f;
dp[0] = 0;
for(int j = 0; j <= 1000000; j++){
for(int i = 1; i <= n; i++){
if(j >= a[i]){
dp[j] = min(dp[j], dp[j-a[i]]+1);
}
}
}
for(int j = 0; j <= 1000000; j++){
if(dp[j] <= k){
printf("%d ", j+t*k);
}
}
printf("\n");
return 0;
}