怎么有关股票的都没人写题解啊
其实买卖k次和买卖2次的本质是相同的。
设f[0/1][j][i]表示只考虑前i支股票,买卖了j次,当前没有/有股票的最大收益
转移:f[0][j][i]=max(f[0][j][i−1],f[1][j][i−1]+x)
f[1][j][i]=max(f[1][j][i−1],f[0][j−1][i−1]−x)
时空复杂度O(nk)
一提交,诶怎么MLE了。。用滚动数组优化掉i的一维,将空间复杂度降为O(k)(类似01背包,j的循环需要倒序)
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
#define MAXK 111
ll f[2][MAXK];
int main()
{
ll n,k,x;
scanf("%lld%lld",&n,&k);
memset(f,0xcf,sizeof f);
f[0][0]=0;
for(ll i=1;i<=n;++i)
{
scanf("%lld",&x);
for(ll j=k;j;--j)
{
f[0][j]=std::max(f[0][j],f[1][j]+x);
f[1][j]=std::max(f[1][j],f[0][j-1]-x);
}
}
ll ans=0;
for(ll i=0;i<=k;++i)ans=std::max(ans,std::max(f[0][i],f[1][i]));
printf("%lld",ans);
return 0;
}
好像定义的i不太对? 题目里说的是 > 给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 ii天的价格。 所以这里股票一共只有一支, 所以用”只考虑前i只股票”的定义是不对的.
聚聚好强!