先表扬y总出题顺序很好!
在上一题中,我们用f[0/1][i]表示只考虑前i支股票且手头有/没有股票的最大收益
这题也是类似的:
f[0][i]:从来没有买过股票的最大收益
f[1][i]:第一次买股票的最大收益
f[2][i]:卖掉一次股票的最大收益
f[3][i]:卖掉一次股票,又买了一次的最大收益
f[4][i]:卖掉两次股票的最大收益
转移时无非是 不动/买/卖,这里就不大篇幅写了,可见代码
时空复杂度O(n)
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
#define MAXN 200011
ll f[5][MAXN];
int main()
{
memset(f,0xcf,sizeof f);
ll n;
scanf("%lld",&n);
f[0][0]=0;
for(ll i=1;i<=n;++i)
{
ll x;
scanf("%lld",&x);
f[0][i]=f[0][i-1];
f[1][i]=std::max(f[1][i-1],f[0][i-1]-x);
f[2][i]=std::max(f[2][i-1],f[1][i-1]+x);
f[3][i]=std::max(f[3][i-1],f[2][i-1]-x);
f[4][i]=std::max(f[4][i-1],f[3][i-1]+x);
}
printf("%lld",std::max(f[0][n],std::max(f[2][n],f[4][n])));
return 0;
}
希望在题解里看到更多想大佬这样透彻的答案~
想问下大佬,为什么要初始化为0xcf呢,我将数组初始化为零为什么是错的呢
比如说第一次买股票的时候,即f[1][i]应该是负值,初始化为零程序考虑不到这些负值
好的,谢谢啦
%%%
讲的很透彻,大佬tql,不愧是狙击y总的大佬
hh太过奖了Orz