upd on 2022.4.6:远古时期的文章,对排版做了亿点优化
分析
大致思路:
dp,将问题的状态刻画下来(在这里,我们将卖出一次股票记为一次完整的交易)
$f(i,j,op)$ 分别表示 第 $i$ 天,已经交易的数量 $j$,当前没有(0)/持有股票(1)
于是得到状态转移方程:
$$f(i,j,0)=max(f(i-1,j-1,1)+w_{i},f(i-1,j,0))$$
$$f(i,j,1)=max(f(i-1,j,0)-w_{i},f(i-1,j,1))$$
解释:如果第i天没有股票,说明可能是前一天也没有,也可能是在第 $i$ 天将股票卖掉了;
解释:如果第i天有股票,说明可能是前一天也有,也可能是在第 $i$ 天将股票买入了;
关于初始化:因为这道题是求 $max$ 的,所以我们可以通过将f初始化为 $-∞$ 以达到“封锁状态”的目的,
比如这道题,在最开始(第 $0$ 天)的时候,其他状态都是“锁死”的,只有 $f(0,0,0)$ 可以转移(因为没有交易也没有持有股票)
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5 , M = 105;
int f[N][M][2]; //三维分别表示 第i天 已经交易的数量 当前没有/持有股票
int w[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>w[i];
memset(f,0xcf,sizeof f); //将f全部初始化为 -∞
f[0][0][0]=0; //第0天初始化为0
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
f[i][j][0]=f[i-1][j][0];
if(j>=1) f[i][j][0]=max(f[i][j][0],f[i-1][j-1][1]+w[i]);
f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0]-w[i]);
}
}
int res=0;
for(int i=0;i<=k;i++) res=max(res,f[n][i][0]);
cout<<res;
return 0;
}
tql