题解：P5662 [CSP-J2019] 纪念品

· · 题解

P5662 [CSP-J2019] 纪念品题解

前言

虽然这道题的题解提交通道已经关闭，但是这道题实在是值得写一篇题解。我看完题目以后一脸懵b，听完老师的讲解才知道如此简单。

思路

完全背包。既然是背包，就要找到质量 w 和价值 v。对于本题，w 表示纪念品的价格。w 每天都会变，因此我们将 w 扩大到2维，即 w_{i,j} 表示第 i 天第 j 件纪念品的价格，也就相当于题目中所给的 P 数组。问题来了，什么表示 v？这就需要我们将问题简化：假设第 i 天买完以后第 i+1 天立刻卖出，即使第 i+2 天卖出赚的更多，也可以选择第 i+1 天再买，第 i+2 天卖出。于是，我们定义 v_{i,j}=w_{i+1,j}-w_{i,j}，表示第 i 天买入第 j 件纪念品后第 i+1 天卖出的收益。这样，完全背包外面再套一层循环表示天数，每天收益加一起，本题结束。

状态转移方程
dp[k]=max(dp[k],dp[k-w[i][j]]+(w[i+1][j]-w[i][j]))

代码

#include <bits/stdc++.h>
using namespace std;
//注意dp数组不是开到m，因为总钱数每天都会变
//题面： 对于100%的数据，小伟手上的金币数不可能超过10^4
int w[110][110],dp[10010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t,n,m;
    cin>>t>>n>>m;
    for (int i=1;i<=t;i++){
        for (int j=1;j<=n;j++){
            cin>>w[i][j];
        }
    }
    //从第1天到第t-1天进行交易，第t天只负责卖
    for (int i=1;i<t;i++){
        memset(dp,0,sizeof dp);
        //完全背包，n件物品，m枚金币
        for (int j=1;j<=n;j++){
            for (int k=w[i][j];k<=m;k++){
                //dp[k]在第i天买入第j件物品后的最大总钱数
                //dp[k-w[i][j]]在第i天买入第j件物品前的最大总钱数
                //w[i+1][j]-w[i][j]在第i天买入第j件物品后在第i+1天卖出的最大收益
                dp[k]=max(dp[k],dp[k-w[i][j]]+(w[i+1][j]-w[i][j]));
            }
        }
        //今天的总钱数再加上明天的收益就是明天的起始钱数
        m+=dp[m];
    }
    cout<<m;
    return 0;
}
双倍经验

P2938 [USACO09FEB] Stock Market G