显然的dp题。
设f[i]表示考虑前i个建筑能获得的最大价值?
无法满足不选相邻的。
如何满足不选相邻的?
设f[0][i]表示考虑前i个建筑,且不选i的最大价值;f[1][i]表示考虑前i个建筑且选了i的最大价值
那么转移就很显然了:
$$f[0][i]=max(f[1][i-1],f[0][i-1])$$
$$f[1][i]=f[0][i-1]+a[i]$$
时间复杂度$O(nT)$,空间复杂度$O(n)$(可以使用滚动数组,但没必要)
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
#define MAXN 100011
ll f[2][MAXN];
int main()
{
ll t,n,x;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
memset(f,0,sizeof f);
for(ll i=1;i<=n;++i)
{
scanf("%lld",&x);
f[1][i]=f[0][i-1]+x;
f[0][i]=std::max(f[1][i-1],f[0][i-1]);
}
printf("%lld\n",std::max(f[0][n],f[1][n]));
}
return 0;
}