题解 | #jzgg，云哥，沙烬巨巨为什么这么强#

这个题读明白了就会发现就是lis预处理一下然后进行区间dp的板子题

//标程
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1110;
const int INF = 0x3f; //初始化的最大值
long long sum[maxn];
long long a[maxn];
long long dp[maxn][maxn];

long long LIS(string s) {
    long long lis[maxn] = {0};
    long long ans = 0;
    long long len = s.size();
    for(int i = 0; i < len; i++)
        lis[i] = 1;
    for (int i = 1; i <= len; i++)
        for (int j = 0; j < i; j++)
            if (s[j] < s[i])
                lis[i] = max(lis[i], lis[j] + 1);
    for (int i = 0; i < len; i++)
        ans = max(ans, lis[i]);
    return (ans * len * int(s[0]));
}

int main(void) {
    int n;
    cin >> n;
    memset(dp, INF, sizeof dp);
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        a[i] = LIS(s);
        sum[i] = sum[i - 1] + a[i];
        dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1, j = len; j <= n; i++, j++) {
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}