题解 CF19B

· · 题解

题目传送门

题目分析

本题是01背包的变形

从题目中我们可以得知一件商品 i 扫描需要 t_i 时间。

那么在扫描这件物品的同时我们可以偷走 t_i 件物品。

也就是说，扫描物品 i 一共能得到 t_i+1 件物品。

那么问题就可以转化成这样的背包问题：

一共有 n 件物品，第 i 件物品的体积为 t_i+1，价值为 c_i。

那答案要去求的是什么呢？

假设我们一共付了 k 个物品的钱，那么在前 k-1 件物品中，

我们为了尽可能地得到更多的物品，会将能偷到的 t_i 全部偷过来。

但到了扫描第 k 件物品的时候，我们可能已经不需要全部偷过来了。

所以答案要求的是得到至少 n 件物品所需的最小价值。

因此我们可以推出背包的最大容量为 t_{\max}+n。

然后我们来观察一下数据范围：

1≤n≤2000$，$1≤c_i≤10^9

考虑当所有物品扫描时间 t 都为 0 时一件都偷不走。

此时答案的极限值为：2000*10^9=2*10^{12}。

因此 ans 的初始值要设置为 2*10^{12}，我们需要开 longlong。

代码

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
typedef long long ll;
const int M=2005,N=4005;
int n,t[M],v;
ll c[M],dp[N],ans=2e12;//注意ans的初始值 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%lld",&t[i],&c[i]);
        t[i]++;//将t数组转换为用来存物品"体积" 
        v=max(v,t[i]);
    }
    v+=n;//算出最大体积 
    memset(dp,0x7f,sizeof(dp));dp[0]=0;//对dp数组进行初始化 
    for(int i=1;i<=n;i++)
        for(int j=v;j>=t[i];j--)
            dp[j]=min(dp[j],dp[j-t[i]]+c[i]);//01背包 
    for(int i=n;i<=v;i++)
        ans=min(ans,dp[i]);//在所有满足条件的物品个数中寻找耗费最少的方案 
    printf("%lld",ans);
    return 0;
}

看懂了别忘点个赞在走ya