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

解题思路

这道题显然是一道动态规划的题目，但是为什么呢？ 首先，动规求解的一般问题（尤其是线性和背包问题）大多要具备以下几个特征：

1. 最优子结构：原问题的最优解包含子问题的最优解。
2. 子问题重叠：有大量的子问题被重复求解。
3. 无后效性。在动态规划中会把原问题分解为若干个子问题，将每个阶段的子问题的求解过程都作为一个阶段，在完成前一阶段后，根据前一阶段的结果求解后一阶段。

对于这个问题，因为交易间隔和次数不做限制，也就是相当于每次交易只与钱够不够有关，与之前怎么做的无关。

所以我们只要每天收益最大化就可以做到总收益最大化了，不需要关心买了什么、买了几次，因为这不会影响到后面的求解。

确定了是动态规划，接下来就是动态转移方程。

还是因为交易间隔和次数不做限制，所以我们完全可以买东西一天就脱手卖了，需要时再买回来。
于是第 $i$ 天买第 $j$ 件物品并且第二天就买掉的收益就是：

$$P[i+1][j]-P[i][j]$$

之后就是一个背包模版题了，重量就是买时的价格。

由此得到转移方程（其中 $k$ 是当前手上有的钱）：

$$dp[i][j][k]=\max(dp[i][j-1][k],dp[i][j-1][k-P[i][j]]+P[i+1][j]-P[i][j])$$

当然，这里数据范围不小，空间可能不够用，不过我们就可以从小到大枚举，转移方程就可以优化为：

$$dp[k]=\max(dp[k],dp[k-P[i][j]]+P[i+1][j]-P[i][j])$$

注意第 $T$ 天不需要再枚举（而且这时也没有下一天的价格了）。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int v[maxn],w[maxn],dp[10005];
int p[maxn][maxn];
int t,n,m;
int main() {
	cin>>t>>n>>m;
	for(int i=1;i<=t;i++){
		for(int j=1;j<=n;j++){
			cin>>p[i][j];
		}
	}
	for(int i=1;i<t;i++){
		for(int j=1;j<=n;j++){
			w[j]=p[i+1][j]-p[i][j];//处理收益
			v[j]=p[i][j];
		}
    //接下来就是板子了
		memset(dp,0,sizeof dp);
		for(int j=1;j<=n;j++){
			for(int k=0;k<=m;k++){
				if(v[j]<=k){
					dp[k]=max(dp[k],dp[k-v[j]]+w[j]);
				}
			}
		}
		//m+=max(0,dp[m]);
		//可以选择不卖，此时收益为0。
		//但这里的取最大其实是多此一举,因为计算时已经和初始值0比较过了。
		m+=dp[m];
	}
	cout<<m;
	return 0;
}