AcWing 1057. 股票买卖 IV
原题链接
中等
作者:
wangyj
,
2021-01-17 20:16:36
,
所有人可见
,
阅读 335
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,w[100005],f[100005][105][2],i,j,ans=0;
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&w[i]);
memset(f,-0x3f,sizeof f);
for(i=0;i<=n;i++)f[i][0][0]=0;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]),f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
for(i=0;i<=m;i++)ans=max(ans,f[n][i][0]);
printf("%d\n",ans);
return 0;
}