dp+单调队列/dp+记录最大值
状态定义:以i为结尾的松散子序列最大值
状态计算:dp[i-2]及之前的状态都可更新dp[i]
根据状态计算很容易想到保留一下前i-2个dp序列最大值由单调队列即可甚至用一个数值记录都可以
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e6+10;
const LL mod=1e9+7;
LL n,m,a[N],dp[N];
string s;
void solve(){
cin>>s;
LL n=s.size();
s=' '+s;
for(int i=1;i<=n;i++){
a[i]=s[i]-'a'+1;
}
dp[1]=a[1],dp[2]=a[2];
deque<LL> q;
LL res=a[2];
q.push_back(a[1]);
for(int i=3;i<=n;i++){
dp[i]=q.front()+a[i];
while(q.size()&&q.back()<res)q.pop_back();
q.push_back(res);
res=dp[i];
}
LL ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
由上代码可发现我们只需要队列最大值,所以用最大值就太浪费了
直接用一个最大值记录即可
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e6+10;
const LL mod=1e9+7;
LL n,m,a[N],dp[N];//以i为结尾的松散子序列最大值
string s;
void solve(){
cin>>s;
LL n=s.size();
s=' '+s;
for(int i=1;i<=n;i++){
a[i]=s[i]-'a'+1;
}
dp[1]=a[1],dp[2]=a[2];
LL res=a[2],mx=a[1];
for(int i=3;i<=n;i++){
dp[i]=mx+a[i];
mx=max(mx,res);
res=dp[i];
}
LL ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}