JZOJ 4227 B

Orz matthew99 良心出题人！

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

但是注意到一个问题，在比较字典序的时候，如果第一位相同，就要继续比较第二位。
如果转移时 k 取到了 j，但后缀 SAi−1+1 比后缀 SAi+1 大，则不能通过 k 转移。

然后就随便统计下答案。

代码：

#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);
}