额外提供一种空间复杂度O(1) 的做法

这一篇题解的优化依然没有到尽头。

我们发现在转移中，

f_{i,\cdots}

只和

f_{i-1,\cdots}

相关，所以可以直接把

i

这一维压掉。

然后发现

a_i

也没啥存的必要性，也压掉。

空间复杂度

O(1)

了。

CPP

#include <stdio.h>
#include <algorithm>
using std::max;
long long f[2][3]; 
int main()
{
	int n,i,x;
	scanf("%d %d",&n,&x); 
	f[1][2]=x;
	for(i=2;i<=n;++i)
	{
        scanf("%d",&x);
		f[i&1][0]=max(f[!(i&1)][1],f[!(i&1)][i%2*2]);
		f[i&1][1]=i%2*x+f[!(i&1)][!(i%2)*2];
		f[i&1][2]=f[!(i&1)][i%2]+x;
	}
	printf("%lld\n",max(f[n&1][!(n%2)*2],f[n&1][1]));
}

额外提供一种空间复杂度O(1) 的做法

讨论操作

回复

相关推荐

额外提供一种空间复杂度O(1) 的做法