[CSP-J2019] 纪念品 题解

· · 个人记录

思路

不难发现这是一道DP，而且看起来是背包问题。

这道题有一个难点，小伟今天买的东西不知道在第几天卖出。

如果这道题是背包的话，那么买的物品必须当天买，明天卖。

那么，思考到这里，就不难想到了：

我们可以当天买，明天卖。而且明天我们还可以原价买回，就等于明天没有卖。

不妨想到背包的三要素：

1.容量：今天手里有的钱。

2.价值：这个货物明天和今天的价值差。

3.重量：今天的价值。

设 dp_i 为当手里有的钱为 i 的时候，最多能赚多少钱。

状态转移方程：

dp_j=\max(dp_j,dp_{j-p_{k,i}}+(p_{k+1,i}-p_{k,i}))

其中，k 是枚举第几天， i 是枚举 第 k 天 每个货物的价值，p_{i,j} 是第 i 天，第 j 个货物的价值。

循环的最后，将手头的钱加上能得到的最优的钱数\max(dp_i) 即可。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>

using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N=1e3+10;//注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f;

int n;
int a[N],dp[N*10];
int p[N][N];

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int t,n,m;
    cin>>t>>n>>m;
    for(int i=1;i<=t;i++){
        for(int j=1;j<=n;j++) cin>>p[i][j];
    }
    for(int k=1;k<t;k++){
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            for(int j=p[k][i];j<=m;j++) dp[j]=max(dp[j],dp[j-p[k][i]]+(p[k+1][i]-p[k][i]));
        }
        m+=dp[m];
    }
    cout<<m;
    return 0;
}