AcWing 1057. 股票买卖 IV
原题链接
中等
作者:
小竹笋
,
2024-04-13 09:49:40
,
所有人可见
,
阅读 1
思路
f[i][j][k]从前i个股票中选,在进行第j次交易,当前的状态是k
状态k:k=0空仓(手里没有股票) k=1持仓(手中有股票)
初始化:f[0][j][0]=0,其余-INF,因为在第0个股票一定是无货的,必定从这个位置开始转移才有效
k=0 -> k=0 手中没股票且不买 f[i-1][j][0]
k=0 -> k=1 手中没股票买了 f[i-1][j][0]-w[i]
k=1 -> k=0 手中有股票卖掉 f[i-1][j-1][1]+w[i](j-1的原因:一次买入卖出为一次交易)
k=1 -> k=1 手中有股票且不卖 f[i-1][j][1]
f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1])
f[i][j][1] = max(f[i-1][j][0]-w[i],f[i-1][j][1])
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;//股票n天的价格,最多可以完成m笔交易
const int N = 100010, M = 110, INF = 0x3f3f3f3f;
int a[N];
int f[N][M][2];
//f[i][j][k]从前第i天中选,在进行第j次交易,k为状态
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(f, -0x3f, sizeof f);
for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]+a[i]);
f[i][j][1] = max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);
}
}
int res = 0;
for(int i=0;i<=m;i++){
res = max(res,f[n][i][0]);
}
printf("%d\n",res);
return 0;
}