题解 P5662 【纪念品【民间数据】】
ShineEternal
2019-11-23 09:02:43
[好东西](https://blog.csdn.net/kkkksc03/article/details/103210336)
# 题意简述：
给定⼀个$D$天的$S$只股票价格矩阵，以及初始资⾦ $M$；每次买股票只能买某个股票价格的整数倍，可以不花钱，约定获利不超过$500000$。最⼤化你的 总获利。
# 题目分析：
首先我们要知道此题的详细意图：每天都可以用你手中有的钱买入股票，数量不限，也可以卖出你自己的股票，所得的收益或价值已经在$D*S$的矩阵中给出。要求在最后一天结束后得到的钱最多。
# 题解：
其实我们可以发现：对于每一天只要最大化你的收益就可以达成目的。然后问题就转换为求每一天的股票交易情况了。又知道每个股票可以无限量的购买（当然价值和不多于手中的钱），显然，就是一个完全背包。
##### 其实题目中的获利不超过$500000$已经暗中提示了DP等算法的使用，因为给出一个不是由$int$到$long$ $long$ 的数据范围的改变一定是为数组内存准备的。
> ⾸先每天结束之后剩下的钱尽量多肯定是最优的。
因为连续持有股票相当于每天买完以后，第⼆天
卖掉然后再买。所以就可以每天做⼀次完全背包。
时间复杂度$O(700000*D*S)$。
接下来就不再赘述了，其他部分会在代码中注明，看代码：
# 代码：
```
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int a[61][21],f[500005];
int main()
{
int s,d,m;
scanf("%d%d%d",&s,&d,&m);
for(int i=1;i<=s;i++)
{
for(int j=1;j<=d;j++)
{
scanf("%d",&a[i][j]);
}
}//以上不需要解释
for(int k=2;k<=d;k++)
{
memset(f,0,sizeof(f));
int maxx=0;
for(int i=1;i<=s;i++)
{
for(int j=a[i][k-1];j<=m;j++)//每次循环到前一天当前位置的股票交易价格。
{
f[j]=fmax(f[j],f[j-a[i][k-1]]+a[i][k]-a[i][k-1]);//第一种情况是不买，第二种就是买：要价格减去买入所花的钱再加上今天和昨天的价格差，因为如果不卖出相当于卖出再买入
maxx=fmax(f[j],maxx);//取出一天股票的最大值
}
}
m+=maxx;//累加收益
}
printf("%d",m);
return 0;
}
```
# 以上是原题P2938的解法
但是观察这道题仅仅是把输入顺序和数据范围微调，且没有实质上的改变，所以
```cpp
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int a[105][105],f[10005];
int main()
{
int s,d,m;
scanf("%d%d%d",&d,&s,&m);
for(int i=1;i<=d;i++)
{
for(int j=1;j<=s;j++)
{
scanf("%d",&a[j][i]);
}
}//以上不需要解释
for(int k=2;k<=d;k++)
{
memset(f,0,sizeof(f));
int maxx=0;
for(int i=1;i<=s;i++)
{
for(int j=a[i][k-1];j<=m;j++)//每次循环到前一天当前位置的股票交易价格。
{
f[j]=fmax(f[j],f[j-a[i][k-1]]+a[i][k]-a[i][k-1]);//第一种情况是不买，第二种就是买：要价格减去买入所花的钱再加上今天和昨天的价格差，因为如果不卖出相当于卖出再买入
maxx=fmax(f[j],maxx);//取出一天股票的最大值
}
}
m+=maxx;//累加收益
}
printf("%d",m);
return 0;
}
```
即可，这里需要注意f数组要开成题目保证不超过的范围，而不是读入的m的范围