CF632E Thief in a Shop

题目链接：http://codeforces.com/contest/632/problem/E

题目大意：

　　从 (n) 个不同的数中取 (k) 个（可重复取）并加起来，问最多能得到多少种不同的和，从小到大输出所有的和。

　　（(1 le n,k,a_i le 1000)）

知识点：　　DP

解题思路：

　　首先明确一点：对于 (5s) 的时限，(O(1e9)) 的复杂度是可以过的，因此我们可以来考虑 (DP).

　　具体的方法是：先把 (a[]) 数组从小到大排序，将 (a[0]) 视为 (0)，即零点上移 (a[0])，则 (a[]) 数组中其他的数也要相应地减掉 (a[0])。对这个零点上移 的数组做 (dp)，使得对每一个和所用的数的个数尽可能少，最后打印答案的时候再将零点复位，则对于需要数的个数小于等于 (k) 的和我们都是可以用 (a[]) 数组中的 (k) 个数取到的（此时 (0) 又变回了 (a[0])）。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1004,inf=0x3f3f3f3f;

int dp[maxn*maxn];
int a[maxn],da[maxn];

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<=1000*k;i++)  dp[i]=inf;
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    sort(a,a+n);

    for(int i=1;i<n;i++)
        da[i]=a[i]-a[0];
    dp[0]=0;
    for(int i=1;i<n;i++){
        for(int j=0;j<1000*k;j++){
            if(dp[j]<inf)
                dp[j+da[i]]=min(dp[j+da[i]],dp[j]+1);
        }
    }
    
    for(int i=0;i<=1000*k;i++){
        if(dp[i]<=k)
            printf("%d ",i+k*a[0]);
    }printf("
");
    
    return 0;
}