AcWing 1057. 股票买卖 IV
原题链接
中等
作者:
甜菜丘
,
2024-04-07 23:07:54
,
所有人可见
,
阅读 2
//f[i][j][1] 表示只看前i天 正在进行第j次交易 且当前持有股票 的最大收益
//f[i][j][0] 表示只看前i天 已经进行了j次交易 且当前不持有股票 的最大收益
//从无到有算作一个交易进行(j+1),从有到无算作一次交易的结束(j不变)
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10,M=110;
int f[N][M][2];
int main(){
int n,k,w;
cin>>n>>k;
//设置入口 只能从0次交易手中无货转移
memset(f,-0x3f,sizeof f);
for(int i=0;i<=n;i++) f[i][0][0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&w);
for(int j=1;j<=k;j++){
f[i][j][1] = max(f[i-1][j-1][0]-w,f[i-1][j][1]);
f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]+w);
}
}
int res=0;
for(int i=0;i<=k;i++) res=max(res,f[n][i][0]);
cout<<res;
return 0;
}