P5662 CSP-J 2019 纪念品
基本思路
状态方程
满头大汗地想了一个半小时，推导出一个可行的状态方程。
\(F[i][j][k]\)表示第\(i\)天，前\(j\)种纪念品，花费\(k\)金币所能得到的第二天最大卖出价格
状态转移
首先第一维明显可以用滚动数组优化。
然后就是枚举\(k\)时的最大值问题，这里我用一个\(m\)维护一轮中最大的\(F[i][j][k]\)，也是可行的。
我把购买当前物品直接等价成价值先减去本轮物品的价格再加上下一轮该物品的价格，也是可行的。
然而最关键的步骤，状态转移方程，我推不对。
理论上应该有三个状态
- 不操作当前物品（不买不卖）
- \(F[i][j][k] = F[i - 1][j - 1][k]\)
- 这个好说
- 购买当前物品
- \(F[i][j][k] = max(F[i][j][k], F[i - 1][j - 1][?] + w[i + 1][j] - w[i][j])\)
- 这里\(F\)的第三维我犯难了，凭直觉我写了\([k - w[i][j]]\)
- 卖掉当前物品
- \(F[i][j][k] = max(F[i][j][k], F[i - 1][j - 1][?] + w[i][j])\)
- 这里我几乎是没法推出来，无脑写了\([k - w[i - 1][j]]\)
因为第二个第三个状态的模糊，我的代码样例都跑不了。但还是先挂一下。
代码实现
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int T, N, M, m;
int w[110][110];
int F[110][10010];
int main()
{
cin >> T >> N >> M;
m = M;
for (int i = 1; i <= T; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> w[i][j];
}
}
for (int i = 1; i <= T; i++)
{
M = m;
m = 0;
for (int j = 1; j <= N; j++)
{
for (int k = 0; k <= M; k++)
{
F[j][k] = F[j - 1][k];
if (k >= w[i][j])
{
F[j][k] = max(F[j][k], F[j - 1][k - w[i][j]] + w[i + 1][j] - w[i][j]);
//printf("buy the goods F[%d][%d] = %d\n", j, k, F[j][k]);
}
if (k >= w[i - 1][j])
{
F[j][k] = max(F[j][k], F[j - 1][k - w[i - 1][j]] + w[i][j]);
//printf("sell the goods F[%d][%d] = %d\n", j, k, F[j][k]);
}
m = max(m, F[j][k]);
}
}
}
cout << m;
return 0;
}
改进思路
状态方程
题解竟然和我一模一样。
状态转移
这可就太值得说道说道了。
其实我对于不操作当前物品和购买当前物品的状态转移都是完全正确的。
然而第三个状况，也就是卖掉当前物品，不是不对，而是根本不应该考虑。
因为结合我对状态方程的定义
第\(i\)天，前\(j\)种纪念品，花费\(k\)金币所能得到的第二天最大卖出价格
以及我对物品的处理
所有物品的买入等价成第二天最大的卖出价格的增加。
实际上，所有当前我所拥有的物品都已经被当成价格而非物品来考虑了，并且也参与了该轮最大价格的构成。
另一方面，我当时在推导卖掉当前物品时万分别扭就是因为我状态方程的值是下一轮最大的卖出价格，而我卖掉当前物品，获利的是本轮，我无法用一个用来记录下一轮价格的状态来操作本轮的价格变化。
换句话说，所谓卖掉当前物品这个情况，实际上已经被上一轮自动考虑了，即所有购买的物品都被自动卖出了，除非你不选择购买本轮的物品（即花掉上轮自动卖出的钱），否则影响是一直存在的，所以被购买的物品已经在上一轮被操作过了，在本轮不用也不能对它进行二次操作。
代码实现
首先把卖掉当前物品的情况删去。
然后是\(m\)的更新方式要改变，因为状态方程计算的是纯利润，并没有加上本金。所以在每轮天数都用\(m\)加上状态方程更新的最大收益即可。
先贴上这样处理完的代码
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int T, N, M;
int w[110][110];
int F[110][10010];
int main()
{
cin >> T >> N >> M;
for (int i = 1; i <= T; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> w[i][j];
}
}
for (int i = 1; i <= T; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 0; k <= M; k++)
{
F[j][k] = F[j - 1][k];
if (k >= w[i][j])
{
F[j][k] = max(F[j][k], F[j - 1][k - w[i][j]] + w[i + 1][j] - w[i][j]);
}
}
M += F[N][M];
}
}
cout << M;
return 0;
}
然而还是不对，犯了一个严重的错误，又把完全背包和零一背包的处理混淆了。
零一背包从\(F[j - 1][]\)来推自然无可厚非，问题是完全背包写成这个形式是通过比较两个状态推导出来的，本身就不是直接逻辑，由推导得出应该是从\(F[j][]\)推出才对。
终于AC
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int T, N, M;
int w[110][110];
int F[110][10010];
int main()
{
cin >> T >> N >> M;
for (int i = 1; i <= T; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> w[i][j];
}
}
for (int i = 1; i <= T; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 0; k <= M; k++)
{
F[j][k] = F[j - 1][k];
if (k >= w[i][j])
{
F[j][k] = max(F[j][k], F[j][k - w[i][j]] + w[i + 1][j] - w[i][j]);
}
}
M += F[N][M];
}
}
cout << M;
return 0;
}