能量站

思路与复杂度

令 f[j] 为处理当前前缀、选择恰好 j 站且当前站未选的最大能量，g[j] 为当前站已选的最大能量。未选可由前一站两状态转移，已选只能由前一站未选且选择数少1的状态转移。非法状态设负无穷；最终取所有不超过 k 个的状态最大值。时间 O(nk)，空间 O(k)，能量用64位整数。

正确性与边界

相邻不能同时选，因此两种状态覆盖全部合法选择且互不遗漏。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,k;cin>>n>>k;const long long N=-(1LL<<60);vector<long long>f0(k+1,N),f1(k+1,N),g0(k+1),g1(k+1);f0[0]=0;for(int i=0;i<n;i++){long long a;cin>>a;fill(g0.begin(),g0.end(),N);fill(g1.begin(),g1.end(),N);for(int j=0;j<=k;j++){g0[j]=max(f0[j],f1[j]);if(j&&f0[j-1]!=N)g1[j]=f0[j-1]+a;}f0.swap(g0);f1.swap(g1);}long long ans=0;for(int j=0;j<=k;j++)ans=max({ans,f0[j],f1[j]});cout<<ans<<"\n";}