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 }