状态机模型

1.acwing 1057

闫氏DP分析法
状态表示fi,j,kfi,j,k—集合： 考虑前 i 天的股票，第 i 天的 决策 是 k，且完成的 完整交易数 为 j 的方案

状态表示fi,j,kfi,j,k—属性： 方案的总利润 最大MAX

状态计算fi,j,kfi,j,k：

fi,j,0=max(fi−1,j,0,fi−1,j−1,1+wi)

fi,j,1=max(fi−1,j,1,fi−1,j,0−wi)
接下来用 状态机模型 解释一下状态计算

状态机模型DP
第 i 天状态是持仓状态(j=1)，则第 i 天可能产生的行为是 买入行为 或 持仓行为
第 i 天状态是空仓状态(j=0)，则第 i 天可能产生的行为是 卖出行为 或 空仓行为

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int N = 1e5 + 10,M = 110,inf = 1e9;
 5 const int mod = 1e9 + 7;
 6 #define cy cout << "Yes" << endl
 7 #define cn cout << "No" << endl
 8 
 9 int n,m;
10 int w[N];
11 int f[N][M][2];
12   
13 
14 int main() {
15     scanf("%d%d", &n, &m);
16     for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
17 
18     memset(f, -0x3f, sizeof f);
19     for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0; //初始化
20     
21     for (int i = 1; i <= n; i ++ )
22     {
23         for (int j = 1; j <= m; j ++ ){
24         f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j][1] + w[i]);
25         f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j - 1][0] - w[i]);
26         }
27     }
28     
29     int res = 0;
30     for (int i = 1; i <= m; i ++ ) res = max(res,f[n][i][0]); //最后一个一定要为0，表示完整的一次交易
31     
32     cout << res << endl;
33 }