Description:
给你$n$个数可以任取$k$个(可重复取),输出所有可能的和.
$n leq 1000,a_i leq 1000$
Solution:
好神的DP,我们排序后把每个数都减去第一个,那么第一个就变成0,任意取不足k次的j次都是合法的-----多余的可以用第一个补上.不过感觉复杂度不太对啊...CF也真是快啊...
for(i=0;i<=1000000;i++)dp[i]=inf;
dp[0]=0;
for(j=0;j<=1000000;j++){
for(i=1;i<=n;i++){
if(j>=a[i]){
dp[j]=min(dp[j],dp[j-a[i] ]+1);
}
}
}
int flag=1;
for(j=0;j<=1000000;j++)
if(dp[j]<=k){
printf("%d ",j+t*k);
}