b_ali_拼接最长非递减字符串（字符区间dp，阿里21届秋招笔试）

首先定义上升字符串，对于任意的 0<i<len(s) 0<i<len(s)，s[i]≥s[i−1]，比如aaa，abc是，acbd不是
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度
其中 1≤n≤106，字符串的总长度不超过1e6且都由小写字母组成。

4
aaa
abcd
zzz
bcd
输出：13

暴力dp解法（超时）：f[i]表示前i个字符串可拼接的非递减字符串的最大长度
(f[i]=max(f[i], f[j]+A_{j}.length())（j<i && A[j].back()<A[i].front()）)

O(nlogn)解法，(f[i])表示以字符(i)结尾的最长非下降字符串的长度

#include<bits/stdc++.h>
using namespace std;
const int N=26;
int n, f[N];
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    string A[n]; for (int i=0; i<n; i++) cin>>A[i];
    sort(A,A+n,[&](string a, string b){return a[0]<b[0];});
    for (string& s : A) 
    for (int i=s.back()-'a', x=s.back()-'a'; ~i; i--) {
        int j=s[0]-'a';
        if (i<=j) f[x]=max(f[x], f[i]+(int)s.size()); //字符串s（即字符j≥字符i）可以接在字符i后面
        else      f[x]=max(f[tx, f[i]); //否则，f[t]就和f[i]取个最优
    }
    cout<<*max_element(f,f+N);
    return 0;
}   

优化解法（借鉴的)：f[i][j]表示以字符i开始，以字符j结尾的最长非递减字符串的长度
对于一个长度为len的字符串，开头为c，结尾为f，则它 f[c][f]=len，
但我们是从多个字符串选出若干个拼接，所以对于字符串s，我们还需用它来更新c之前的字符到f之后已有的状态
(f[i][j]=max(f[i][j], f[i][c]+len+f[f][j])（i≤c && j≥f))

#include<bits/stdc++.h>
using namespace std;
const int N=26;
int n, f[N][N];
void update_dp(string& str) {
    int s=str.front()-'a', e=str.back()-'a', len=str.length();
    for (int i=0; i<=s; i++)
    for (int j=25; j>=e; j--) {
        if (s==e) f[i][j]+=len;
        else f[i][j]=max(f[i][j], f[i][s]+len+f[e][j]);
    }
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n; 
    while (n--) {
        string s; cin>>s;
        update_dp(s);
    }
    cout<<f[0][25];
    return 0;
}