AcWing 5406. 松散子序列
原题链接
中等
作者:
奈奈生
,
2024-04-13 13:01:48
,
所有人可见
,
阅读 3
算法1
(线性DP-1) $O(n^2)$
f[i]表示以第i个字母结尾的所有方案的最大值,只过了三个数据
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N=1e6+10;
char a[N];
int f[N],re;//f[i]表示以第i个字母结尾的所有方案的最大值
int main()
{
scanf("%s",a+1);
f[1]=a[1]-96;
f[2]=a[2]-96;
int n=strlen(a+1);
for(int i=3;i<=n;i++)
{
for(int j=2;j<i-1;j++)
{
f[i]=max(f[i],f[i-j]+a[i]-96);
}
}
for(int i=1;i<=n;i++)
re=max(re,f[i]);
cout<<re;
return 0;
}
算法2
(线性DP-2) $O(n)$
f[i]表示前i个字母的所有方案的最大值
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N=1e6+10;
char a[N];
int f[N],re;
int main()
{
scanf("%s",a+1);
f[1]=a[1]-'a'+1;
int n=strlen(a+1);
for(int i=2;i<=n;i++)
{
f[i]=max(f[i-1],f[i-2]+a[i]-'a'+1);//max(不选第i个字母,选第i个字母)
}
cout<<f[n];
return 0;
}
算法2
(状态机) $O(n)$
f[i][0/1]表示第i个字母选or不选
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N=1e6+10;
char a[N];
int f[N][2];
int main()
{
scanf("%s",a+1);
int n=strlen(a+1);
for(int i=1;i<=n;i++)
{
f[i][0]=max(f[i-1][0],f[i-1][1]);//f[i][0]表示第i个字母不选的最大值,那就等于第i-1个字符选或者不选的最大值
f[i][1]=f[i-1][0]+a[i]-'a'+1;//f[i][1]表示第i个字母选的最大值,那就等于第i-1个字符不选+第i个字符的权重
}
cout<<max(f[n][0],f[n][1]);//max(最后一个字符选还是不选)
return 0;
}