CF19B Checkout Assistant 题解
题目链接:CF19B Checkout Assistant
:Bob 来到现购自运商店,会 n n n 把货物放进他的手推车里,然后到收银台付款。每件商品的价格由它的价格决定 c i c_i ci 与收银员一起扫描时间 t i t_i ti 秒定义。
收银员在扫描商品时,Bob 一些其他商品可以从他的手推车里偷走。Bob 需要恰好 1 1 1 偷一件商品几秒钟。Bob 最少要付给收银员的钱是多少?请记住,收银员扫描商品的顺序是由 Bob 决定。
这个问题真的有点难想,因为它的背包容量和物品都与 n n n 有关的
观察问题的性质,我们需要带走一切 n n n 件物品
而第 i i i 物品可以花 c i c_i ci 的价格带走 t i 1 t_i 1 ti+1 件物品
为什么是 + 1 +1 +1 ?因为它本身也会被带走
题目要求的是带走这 n n n 件物品的最小花费,可以看出这是一个01背包
但是背包的大小并不是很好确定
因为选择的物品它们的 ∑ ( t i + 1 ) \sum (t_i+1) ∑(ti+1) 很可能会超过 n n n
那么最多会超过多少呢?不难发现背包容量最多为 n + max ( v i ) + 1 n+\max(v_i)+1 n+max(vi)+1
如果超过了这个数,那么当前的选择一定不是优的
由于我们并不知道最后会超过多少,我们就把每一种情况都算出来,然后取个 min \min min 就好了
设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示只考虑前 i i i 件物品,恰好装满 j j j 时的最小花费,则有 d p [ i ] [ j ] = min ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − t i − 1 ] + c i ) dp[i][j]=\min(dp[i-1][j],dp[i-1][j-t_i-1]+c_i) dp[i][j]=min(dp[i−1][j],dp[i−1][j−ti−1]+ci) 滚动数组一下,就是 d p [ j ] = min ( d p [ j ] , d p [ j − t i − 1 ] + c i ) dp[j]=\min(dp[j],dp[j-t_i-1]+c_i) dp[j]=min(dp[j],dp[j−ti−1]+ci) 于是答案就是 min n ≤ i ≤ n + max ( v k ) + 1 ( d p [ i ] ) \min_{n \le i \le n+\max(v_k)+1}(dp[i]) n≤i≤n+max(vk)+1min(dp[i]) 代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
int n,dp[N*2],w[N],v[N],mx;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1; i<=n; i++)
{
cin >> w[i] >> v[i];
++w[i];
mx=max(mx,w[i]);
}mx+=n;
for(int i=1; i<=n; i++)
for(int j=mx; j>=w[i]; j--)
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
int res=INF;
for(int i=n; i<=mx; i++)
res=min(res,dp[i]);
cout << res << endl;
return 0;
}
以上文章写于q779咖啡因摄入过度时,可能有些抽风
所以速溶咖啡不要一口闷