有n种数，每次可以取恰好k个数，一种数可以取无数次，问有哪些可能的和。
最朴素的dp是4方的，我们考虑优化到3方。因为恰好k个数的限制条件有些麻烦，我们将所有数都减去最小的一个数，这样我们可以取少于k个，不足的就取最小的那个补充。也就是设f[i]表示减掉最小数后凑到和为i至少要f[i]次。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int N = 501; 7 int n, k, a[N], f[N * N]; 8 9 int main() { 10 scanf("%d %d", &n, &k); 11 for (int i = 1; i <= n; i ++) scanf("%d", &a[i]); 12 sort(a + 1, a + n + 1); 13 for (int i = 2; i <= n; i ++) a[i] -= a[1]; 14 for (int i = 1; i <= k * a[n]; i ++) f[i] = k + 1; 15 for (int i = 2; i <= n; i ++) 16 for (int j = a[i]; j <= k * a[n]; j ++) f[j] = min(f[j], f[j - a[i]] + 1); 17 for (int i = 0; i <= k * a[n]; i ++) if (f[i] <= k) printf("%d ", i + a[1] * k); 18 return 0; 19 }
CODEFORCES #632 E. Thief in a Shop
原文：http://www.cnblogs.com/awner/p/5778054.html