今天发绿题题解

读过题目后 我们发现：

（哦 这还用读过吗？）

这是一道完全背包的题 我们进行 t − 1 轮完全背包:

• 把今天手里的钱当做背包的容量

• 把商品今天的价格当成它的消耗

• 把商品明天的价格当做它的价值

每一天结束后把总钱数加上今天赚的钱 直接写背包模板即可

另附： 在这道题中 我们可以把商品和钱看成同样的东西 因为题目中说了：

可以当天买当天卖 所以不必考虑跨天的买卖 只需考虑当天的即可 这满足动态规划对于最优化原理和无后效性的要求 可以大胆地购买

(感觉好正经的样子)

AC代码！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 101;
const int M = 10001;
int n, m, t, price[N][N], f[M];
int main(){
	cin >> t >> n >> m;
	for(int i = 1; i <= t; i++)
		for(int j = 1; j <= n; j++)
			cin >> price[j][i];
          //读入每种商品每天的价格
	for(int k = 1; k < t; k++){
		memset(f, 0, sizeof f);//每轮开始前都要制零
		for(int i = 1; i <= n; i++)
			for(int j = price[i][k]; j <= m; j++)//完全背包,正着循环
				f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
      
		m += f[m];//加上盈利的钱，进入下一轮买卖
	}
	cout << m;
	return 0;
}

点个赞吧~