AcWing 1057. 股票买卖 IV

题目传送门

一、画图分析状态机

二、状态机分析法

闫式DP分析法--状态机分析法

• 集合
  \(f[i,j,0]\):只考虑前\(i\)天，且已经进行完\(j-1\)次交易，正在进行第\(j\)次交易，且手中无货的所有购买方式的集合。
  \(f[i,j,1]\):只考虑前\(i\)天，且已经进行完\(j-1\)次交易，正在进行第\(j\)次交易，且手中有货的所有购买方式的集合。

• 属性：最大值

• 状态计算
  根据状态机的图来进行分析写出:

\(f[i,j,0]=max(f[i-1,j,0],f[i-1,j,1]+w[i])\)

\(f[i,j,1]=max(f[i-1,j,1],f[i-1,j-1,0]-w[i])\)

三、实现代码

#include 

using namespace std;
const int N = 100010;
const int M = 110;
int n;          //n天
int k;          //可以完成的最大交易数量
int w[N];       //每一天的股票价格

/**
一次交易的定义：
一次买入卖出合为一笔交易。所以，我们可以理解为：买入完，不算一次交易，必须是卖出后才算一次完整的交易。
这就是下面为什么需要有时用j-1,有时用j的原因，买入：还是上一次的交易，j-1转移过来；卖出：完成本次交易，j转移过来。

f[i,j,0]:前i天，已经进行完j?1次交易，正在进行第j次交易，且手中无货的所有购买方式的集合。
f[i,j,1]:前i天，已经进行完j?1次交易，正在进行第j次交易，且手中有货的所有购买方式的集合。
*/
int f[N][M][2];

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];//读入每一天的股票价格

    //不合法状态初始化成-INF(求最大值更新为—INF,求最小值更新成INF)
    // f[i][0][1] 前i天没有进行交易但手中却有股票是不合法的
    //黄海理解：不能全部初始化为0还有一个思考的方向，就是如果第一天上来买了一些股票，那么钱花了，利润还为负值
    //因为，还没有套现嘛，当然才投入完是负值了，但，这个负值是值得的，是后续依赖的数据，可不能在转化过程中采用
    //max(0,负数）被0干掉！那样就错了，怎么样才能不被干掉呢?就是给一个负无穷意义上就对了。
    memset(f, -0x3f, sizeof f);
    //前i天交易,交易完成次数为0,手中无股票的状态全为0
    for (int i = 0; i <= n; i++) f[i][0][0] = 0;

    //dp打表
    for (int i = 1; i <= n; i++) //遍历每一天
        for (int j = 1; j <= k; j++) { //遍历每一个可以完成的最大交易数量
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
    //我们发现买入不卖一定不是最优解,所以不用枚举f[i][j][1]的状态
    int res = 0;
    for (int i = 0; i <= k; i++) res = max(res, f[n][i][0]);
    //输出
    printf("%d\n", res);
    return 0;
}