前驱

省选-的题开始把我吓懵了

题目

链接

https://www.luogu.com.cn/problem/CF632E

字面描述

题面翻译

有一个小偷进入了一个商店。

像平常一样，他把他的幸运背包带在身上，他的背包里能放 k 个东西。商店里有 n 种产品，每种产品都有无限多个。对于每个第 i 种产品，它的价值是 a[i] 。

小偷很贪婪，所以他会准确地拿 k 个产品（他有可能把某一种产品拿很多个）。

你需要找出所有小偷可能偷走的物品价值之和。

输入输出格式

输入格式：

第一行有两个整数 n 和 k（1<=n,k<=1000）—— 物品的数量和小偷会拿的物品数量。
第二行有 n 个整数，每一个 a[i]（1<=a[i]<=1000) 是从第 1 个到第 n 个物品的价值。

输出格式：

输出一行，所有可能的被偷窃的物品的价值，每两个之间用一个空格分隔。输出应该以一个递增序列输出。

输入输出样例

输入样例#1：

3 2
1 2 3

输出样例#1：

2 3 4 5 6

输入样例#2：

5 5
1 1 1 1 1

输出样例#2：

输入样例#3：

3 3
3 5 11

输出样例#3：

9 11 13 15 17 19 21 25 27 33
翻译贡献者UID：41262

思路分析

基本分析

本题，可读出来每个物品可取无限次 -> 很像完全背包

但是，题目限定恰好取 $k$ 件物品，十分的恶心（同时也是提升的一次机会。
不妨可以看出这道题中件数是代价，而且每件物品的件数均为1（有点小别扭），所以每件物品的代价均为 $1$ ，

单一性反推多样性

之前做的背包题普遍是靠代价推转移方程算价值，但 $d p$ 只会取极值存储，就如函数的单一性，每个 $x$ 对应唯一的 $y$ ,反之拿 $y$ 推 $x$ 是本题不错的选择，因为函数中每个 $y$ 可以对应多个不同的 $x$ 。我之所以用函数来解释 $d p$ ,是因为 $d p$ 本身就是函数。
所以一个代价只能对应一个极端价值，但是一个价值能对应多个代价，取代价最小，这个价值的发展空间才能最大化。

思想迸射

一个不成熟的思路油然而生；
状态定义：定义 $f_i$ 当凑得价值为 $i$ 时，最小所花费的次数

思路一般化处理

先不说 $f_i$ 怎么转移，至少我们可以确定这个 $f$ 数组是没有后效性的。

假设我们有了一个处理好的数组 $f$ ，针对 $\forall i(1 \leq i \leq 1000^2)$
若 $f_i=k$
$\therefore f_i ,绝对可取$
若 $f_i>k$
$\therefore f_i，绝对不可取$
但针对 $f_i <k$
我们不清楚是否能取到，我们需要用一些特殊的处理方式来处理一下。

还来下面将说明这道题，不看 $t j$ 在一个月内都想不出来的处理方法：

加入价值为0的物品

因为这样在转移方程时，会忽略价值为 $0$ 的物品，加入它们不会让最小凑齐数最小。
$\therefore 为了让发展空间最大化，将a数组sort(从小->大)，将\forall a_i( 1 \leq i \leq n)-a_1,让原有a_1变为0.最后针对f_i<k的情况将i+ka_1,凑齐k件物品，将i+ka_1作为最终结果$

状态转移方程： $f_i=\min(f_i,\min(f_{i-a_j}+1)))(1 \leq i \leq 1000^2) (1 \leq j \leq n)$

时间复杂度: $\Omicron(1000^2 \cdot n)$
若 $n 与 1000 同阶$
$\Omicron(n^3) \approx 1e9$
$\approx 1e9$
可以AC
分析结束！

代码实现

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

const int maxn=1e3+10;
const int inf=2e9;
int n,k,cnt;
int a[maxn],f[maxn*maxn],ans[2*maxn*maxn];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=1000000;i++)f[i]=inf;//状态初始化
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);//sort lower->upper
	//计算凑齐价值为i的最小件数
	for(int j=1;j<=n;j++){
		for(int i=a[j]-a[1];i<=1000000;i++){
			if(f[i-(a[j]-a[1])]==inf)continue;
			f[i]=min(f[i],f[i-(a[j]-a[1])]+1);//价值为0物品处理
		}
	}
	//f[i]<=k 对于价值物品的补助
	for(int i=0;i<=1000000;i++){
		if(f[i]<=k)ans[++cnt]=i+k*a[1];
		else continue;
	}
	//sort print
	sort(ans+1,ans+cnt+1);
	for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);
	return 0;
}