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 
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咖啡因摄入过度时，可能有些抽风

所以速溶咖啡不要一口闷

转载请说明出处