JZOJ 4227.B

Orz matthew99 良心出题人!

“最大价值和”很容易想到 DP,显然我们要根据 SA 来转移。
考虑设 fi,jf_{i,j} 表示第 SAiSA_i 位选 jj 的最大价值和。
转移的话,枚举 i,ji,j,并枚举一个不小于 jj 的字符 kk 即你下一位选的字符,然后显然。

但是注意到一个问题,在比较字典序的时候,如果第一位相同,就要继续比较第二位。
如果转移时 kk 取到了 jj,但后缀 SAi1+1SA_{i - 1} + 1 比后缀 SAi+1SA_i + 1 大,则不能通过 kk 转移。

然后就随便统计下答案。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
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);
}