Orz matthew99 良心出题人！
“最大价值和”很容易想到 DP，显然我们要根据 SA 来转移。
考虑设 \(f_{i,j}\) 表示第 \(SA_i\) 位选 \(j\) 的最大价值和。
转移的话，枚举 \(i,j\)，并枚举一个不小于 \(j\) 的字符 \(k\) 即你下一位选的字符，然后显然。
但是注意到一个问题，在比较字典序的时候，如果第一位相同，就要继续比较第二位。
如果转移时 \(k\) 取到了 \(j\)，但后缀 \(SA_{i - 1} + 1\) 比后缀 \(SA_i + 1\) 大，则不能通过 \(k\) 转移。
然后就随便统计下答案。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
const int N = 1e5;
int n,sa[N + 5],rk[N + 5];
long long w[N + 5][30],f[N + 5][30],ans;
char s[N + 5];
struct RND
{
long long x;
long long operator()()
{
x = (x * 100000005 + 1532777326) % 998244353;
return x / 100;
}
} rnd;
int main()
{
scanf("%d%lld",&n,&rnd.x);
for(register int i = 1;i <= n;++i)
scanf("%d",sa + i),rk[sa[i]] = i;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= 26;++j)
w[i][j] = rnd() % (int)1e4;
for(register int i = 1;i <= 26;++i)
f[1][i] = w[sa[1]][i];
for(register int i = 1;i < n;++i)
for(register int j = 1;j <= 26;++j)
for(register int k = 1;k <= (rk[sa[i] + 1] > rk[sa[i + 1] + 1] ? j - 1 : j);++k)
f[i + 1][j] = max(f[i + 1][j],f[i][k] + w[sa[i + 1]][j]);
for(register int i = 1;i <= 26;++i)
ans = max(ans,f[n][i]);
printf("%lld\n",ans);
}