CF632E Thief in a Shop 题解
前驱
省选-的题开始把我吓懵了
题目
链接
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：
5
输入样例#3：
3 3
3 5 11
输出样例#3：
9 11 13 15 17 19 21 25 27 33
翻译贡献者UID：41262
思路分析
基本分析
本题，可读出来每个物品可取无限次 -> 很像完全背包
但是，题目限定恰好取 k k k件物品，十分的恶心（同时也是提升的一次机会。
不妨可以看出这道题中件数是代价，而且每件物品的件数均为1（有点小别扭），所以每件物品的代价均为 1 1 1，
单一性反推多样性
之前做的背包题普遍是靠代价推转移方程算价值，但 d p dp dp只会取极值存储，就如函数的单一性，每个 x x x对应唯一的 y y y ,反之拿 y y y推 x x x是本题不错的选择，因为函数中每个 y y y可以对应多个不同的 x x x。我之所以用函数来解释 d p dp dp,是因为 d p dp dp本身就是函数。
所以一个代价只能对应一个极端价值，但是一个价值能对应多个代价，取代价最小，这个价值的发展空间才能最大化。
思想迸射
一个不成熟的思路油然而生；
状态定义：定义 f i f_i fi当凑得价值为 i i i时，最小所花费的次数
思路一般化处理
先不说 f i f_i fi怎么转移，至少我们可以确定这个 f f f数组是没有后效性的。
假设我们有了一个处理好的数组 f f f，针对 ∀ i ( 1 ≤ i ≤ 100 0 2 ) \forall i(1 \leq i \leq 1000^2) ∀i(1≤i≤10002)
若 f i = k f_i=k fi=k
∴ f i , 绝对可取 \therefore f_i ,绝对可取 ∴fi,绝对可取
若 f i > k f_i>k fi>k
∴ f i ，绝对不可取 \therefore f_i，绝对不可取 ∴fi，绝对不可取
但针对 f i < k f_i <k fi<k
我们不清楚是否能取到，我们需要用一些特殊的处理方式来处理一下。
还来下面将说明这道题，不看 t j tj tj在一个月内都想不出来的处理方法：
- 加入价值为0的物品
因为这样在转移方程时，会忽略价值为 0 0 0的物品，加入它们不会让最小凑齐数最小。
∴ 为了让发展空间最大化，将 a 数组 s o r t ( 从小 − > 大 ) ，将 ∀ a i ( 1 ≤ i ≤ n ) − a 1 , 让原有 a 1 变为 0. 最后针对 f i < k 的情况将 i + k a 1 , 凑齐 k 件物品，将 i + k a 1 作为最终结果 \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作为最终结果 ∴为了让发展空间最大化，将a数组sort(从小−>大)，将∀ai(1≤i≤n)−a1,让原有a1变为0.最后针对fi<k的情况将i+ka1,凑齐k件物品，将i+ka1作为最终结果
状态转移方程： f i = min ( f i , min ( f i − a j + 1 ) ) ) ( 1 ≤ i ≤ 100 0 2 ) ( 1 ≤ j ≤ n ) f_i=\min(f_i,\min(f_{i-a_j}+1)))(1 \leq i \leq 1000^2) (1 \leq j \leq n) fi=min(fi,min(fi−aj+1)))(1≤i≤10002)(1≤j≤n)
时间复杂度: O ( 100 0 2 ⋅ n ) \Omicron(1000^2 \cdot n) O(10002⋅n)
若 n 与 1000 同阶 n与1000同阶 n与1000同阶
O ( n 3 ) ≈ 1 e 9 \Omicron(n^3) \approx 1e9 O(n3)≈1e9
5 s − > ≈ 1 e 9 5s -> \approx 1e9 5s−>≈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;
}
后继
数学是与信息紧密相同的, f r o m from from l o g i c a l logical logical t o to to l o g i c a l logical logical
必须加入好题本。
The End!