Description
小D是雅禮高一著名的神犇，在NOI同步賽中獲得了滿分的優(yōu)異成績，而全國沒有任何其他人獲得如此的成績。
某天晚上，高一內(nèi)部在討論一道題目，然而包括小D之內(nèi)的各種神犇都毫無頭緒，這時候，高二的人贏小T上來給高二進行了精彩的講解。
小D被小T的神犇氣場所折服，他知道小T之所以沒有同步賽滿分是不屑于，于是他決定拜小T為師。
一日小T正在給小D講解后綴數(shù)組。
“把一個字符串的所有非空后綴按字典序從小到大排序，然后按順序排列出后綴的第一個字符在原串中的位置所形成的數(shù)組，就是后綴數(shù)組。如“ababa”的后綴數(shù)組就是{5, 3, 1, 4, 2}?！?br /> 這里的位置從1開始編號，字符串僅包含小寫英文字母。
接著小T給小D講解了它的構(gòu)造過程。
小D畢竟身為同步賽滿分，水平還是不低，他立即舉一反三：既然我們能給定一個字符串，給出他的后綴數(shù)組，那么給定后綴數(shù)組，能不能恢復(fù)字符串呢。
小T說：“這是不行的，這個問題我?guī)啄昵把芯窟^，譬如說，假設(shè)你后綴數(shù)組是{2, 1}，那么原串既可以是“aa”，也可以是“ bb”。然而，我們的確可以提出一些有趣的問題，我記得我小學(xué)的時候，研究過一個問題，給定一個長度為n的數(shù)組A，以及一個n × 26 的矩陣w，所有下標都從1開始，其中w_{i, j}表示第i個位置填第j個小寫字母的價值，現(xiàn)在你需要給出一個長度為n的字符串，使得它的后綴數(shù)組是A，而且它每個位置的價值和最大。}這個問題可不簡單，我小學(xué)的時候研究了整整一節(jié)課。”
小D想了想，覺得自己大概就算在小學(xué)也只要一節(jié)課就想得出來。各位做題人你們會做嗎？

Input
為了減少輸入量，部分數(shù)據(jù)將在程序內(nèi)生成。
有一個隨機數(shù)產(chǎn)生器，有個內(nèi)部變量x初始時為x_0，每次產(chǎn)生隨機數(shù)時它會將x變?yōu)?100000005x + 1532777326) mod 998244353，然后返回x/100取下整。（a mod b 表示a除以 b的余數(shù)，該運算的優(yōu)先級高于加減法。）
輸入一行兩個兩個整數(shù)n, x_0。
首先輸入一個1到n的排列，表示數(shù)組A，A的定義如題所述。
接著你將按照先i遞增，再j遞增的順序生成w_{i, j}。每次生成一個隨機數(shù)r，則w_{i, j} = r mod {10^4}。

Output
為了減少輸出量，你只需要輸出最大的價值和，不需要給出對應(yīng)的字符串。
輸出一行一個整數(shù)表示最大的價值和。

Sample Input
輸入1：
1 493941464
1
輸入2：
2 736594838
1 2
輸入3：
5 910387714
1 2 3 4 5
輸入4：
15 892431401
8 5 9 1 2 7 11 3 14 15 13 10 12 6 4

Sample Output
輸出1：
9490
樣例1解釋：
答案即為權(quán)值最大的字母的權(quán)值，計算得f的權(quán)值為9490最大。前六個字母的權(quán)值依次為5602, 7113, 5633, 756, 8496, 9490。
輸出2：
16658
樣例2解釋：
計算得“sw”的權(quán)值為16658最大，注意雖然“wf” 的權(quán)值是17957，但是它的后綴數(shù)組為{2, 1}，不滿足條件；“ww”的權(quán)值為16935，但由于“w” 的字典序小于“ww” 所以后綴數(shù)組也是{2, 1}。
輸出3：
44455
樣例3解釋：
對應(yīng)的字符串為“hoooq”。
輸出4：
129724

Data Constraint
對于前20%的數(shù)據(jù)，n ≤ 5。
對于前40%的數(shù)據(jù)，n ≤ 15。
對于前60%的數(shù)據(jù)，n ≤ 1000。
對于前100%的數(shù)據(jù)，n ≤ 100000，0 ≤ x_0 ≤ 998244353。保證存在一個僅含小寫英文字母的字符串，使得它的后綴數(shù)組為A。

.
.
.
.
.
分析
設(shè)f[i][j]為排名第i的后綴開頭是j字母的最大權(quán)值。

f[i][j] 由f[i-1][k] 轉(zhuǎn)移而來，轉(zhuǎn)移有兩種情況。

‘a(chǎn)’<=k<j : f[i][j] = max（f[i-1][k] ）+w[a[i]][j]；
k==j
重點是第二種情況怎么處理。

i-1的排名比i前，他們的開頭又一樣，因此i-1的長度比i短。

rank[i]表示第i個位置開始的后綴的排名，rank[a[i]]=i;

只需要判斷rank[ai + 1]是否大于 rank[a[i-1] +1]

具體意思就是

看ai +1 這個位置的后綴排名，是否大于a[i]+1這個位置的后綴排名

若ai+1這個位置的后綴排名大于a[i-1] +1這個位置的后綴排名，那么當(dāng)k==j，兩個字符串前面都加上同樣的字符，字典序大小關(guān)系不變。

k==j :f[i][j] = max(f[i][j] , f[i-1][j] + w[a[i]][j])（rank[ai + 1]> rank[a[i-1] +1]）

時間復(fù)雜度：O(n)
注意i枚舉的是a[i]的下標

.
.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;long long n,x; long long a[100010],f[100010][30]; long long rank[100010],w[100010][30];int main() {scanf("%lld%lld",&n,&x);for (long long i=1;i<=n;i++)scanf("%lld",&a[i]);for (long long i=1;i<=n;i++)for (int j=0;j<26;j++){x=(x*100000005+1532777326)%998244353;w[i][j]=x/100 %10000;}for (long long i=1;i<=n;i++)rank[a[i]]=i;for (long long i=0;i<26;i++)f[1][i]=w[a[1]][i];for (long long i=2;i<=n;i++){for (int j=0;j<26;j++){for (int k=0;k<j;k++)f[i][j]=max(f[i][j],f[i-1][k]+w[a[i]][j]);if (rank[a[i]+1]>rank[a[i-1]+1]) f[i][j]=max(f[i][j],f[i-1][j]+w[a[i]][j]);}}long long ans=0;for (int i=0;i<26;i++)ans=max(ans,f[n][i]);printf("%lld",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10458935.html

總結(jié)

以上是生活随笔為你收集整理的【五校联考3day2】B的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。