cf1562E. Rescue Niwen!

題意：

我們定義一個字符串s1s2s3…sn的展開為:s1,s1s2,s1s2…sn,s2,s2s3,s2s3…sn,…,sn
找到字符串s“擴展”的最大遞增子序列的大小(根據字典序大小比較)

題解：

第一感覺就是求最長上升子序列的變形
按照字典序大小比較規則，s1<s1s2<s1s2…sn
所以相當于對于每個字符，都會有一個已經默認遞增的長度為n-i+1的后綴子序列
比如：
abcde
對于第一個字符a，默認遞增的有a<ab<abc<abcd<abcde
對于第二個字符b,有b<bc<bcd<bcde
等等
但是光這樣沒完事，因為會有重復情況出現：
比如：
acbac
對于第一個字符有：a,ac,acb,acba,acbac
對于第四個字符有：a,ac
會有重復情況，而重復的就是兩個后綴的前綴部分。如果學過后綴數組，就是lcp，減去lcp就是我們要的答案
設dp[i]表示以第i個字符的后綴為結尾的答案
dp[i]初始化為n-i+1
lcp如何求？可以用后綴數組，也可以$n^2$轉移求
我們如何求LCS的，就相同的思路求LCP
如果s[i]==s[j],則lcp[i][j]=lcp[i+1][j+1]+1
其實就是倒著求LCS
然后就是用LCP去更新dp，基本上就是LIS問題
本題就是LIS+LCS

代碼：

// Problem: E. Rescue Niwen! // Contest: Codeforces - Codeforces Round #741 (Div. 2) // URL: https://codeforces.com/contest/1562/problem/E // Memory Limit: 512 MB // Time Limit: 2000 ms // Data:2021-09-03 19:09:08 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef LOCALstartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef LOCALendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 5e3 + 9; int lcp[maxn][maxn]; int dp[maxn]; char s[maxn]; int main() {//rd_test();int t;read(t);while (t--) {int n;read(n);scanf("%s", s + 1);for (int i= n; i >= 1; i--) {for (int j= n; j >= 1; j--) {if (s[i] == s[j])lcp[i][j]= lcp[i + 1][j + 1] + 1;elselcp[i][j]= 0;}}int sum= 0;for (int i= 1; i <= n; i++) {dp[i]= n - i + 1;for (int j= 1; j < i; j++) {int lcplen= lcp[i][j];if (i + lcplen - 1 >= n || s[i + lcplen] <= s[j + lcplen])continue;int len= n - i + 1 - lcplen;dp[i]= max(dp[i], dp[j] + len);}sum= max(sum, dp[i]);}printf("%d\n", sum);}//Time_test(); }

總結

以上是生活随笔為你收集整理的cf1562E. Rescue Niwen!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。