Let bygones be bygones.
Oh, I have.
欢乐 dp 场。总之我们通过神秘方法，一个像样的正解都没有写，获得了三位数的好成绩。
六出祁山
一个有脑子就会写的暴力 dp，定义 \(f_{i, j}\) 表示处理到第 \(i\) 个，高度改为 \(j\)。有 \(f_{i, j} = f_{i - 1, k} + | h_i - j| (|k - j| \leq d)\)。然后这样是 \(O(n d^ 2)\) 的，考虑优化。那么显然只能优化这个状态数，其它的目前还优化不了。然后就有一个非常离谱的优化，感性理解一下，相邻差都不大于 \(d\)，还在 \(h\) 元素的基础上修改，那么是不是最优状态可以是 \(h_i + kd, k \in \mathbb{Z}\) 呢？
然后状态数从 \(d\) 变到了 \(n ^ 2\)。时间复杂度 \(O(n ^ 5)\)。重新看原来的 dp 柿子，\(j\) 固定，\(k\) 显然也固定，那么 \(j\) 每次循环都增加，只需要用滑动窗口维护 \(k\) 就好了。时间复杂度 \(O(n ^ 3)\)。甚至可以 set。
namespace liuzimingc {
const int N = 305, M = 9e4 + 5, INF = 1e9;
#define endl '\n'
#define int long longint n, d, h[N], v, a[N], ans, q[M];
int f[N][M];
vector<int> lsh;int get(int x) {return lower_bound(lsh.begin(), lsh.end(), x) - lsh.begin();
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >> n >> d;for (int i = 1; i <= n; i++) cin >> h[i], v = max(v, h[i]);if (abs(h[1] - h[n]) > (n - 1) * d) return cout << -1 << endl, 0;for (int i = 1; i <= n; i++)for (int j = -n; j <= n; j++) {int x = h[i] + j * d;if (x >= 0 && x <= v) lsh.push_back(x);}sort(lsh.begin(), lsh.end());lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());memset(f, 0x3f, sizeof(f));f[1][get(h[1])] = 0;for (int i = 2; i <= n; i++) {int head = 1, tail = 0, r = 0;for (int j = 0; j < lsh.size(); j++) {while (head <= tail && lsh[q[head]] < lsh[j] - d) head++;while (r < lsh.size() && lsh[r] <= lsh[j] + d) {while (head <= tail && f[i - 1][q[tail]] > f[i - 1][r]) tail--;q[++tail] = r++;}f[i][j] = f[i - 1][q[head]] + abs(lsh[j] - h[i]);}}cout << f[n][get(h[n])] << endl;return 0;
}
#undef int
} // namespace liuzimingc
水淹七军
糊里糊涂，总之用了一个完全不知道的 Mirsky（Dilworth）定理：\(S\) 的最长链长度等于最小的反链覆盖数。
然后转换成这个，然后就开始分层 dp 了。是的我是 C 的，现在都没懂，我骄傲😊（假的其实半懂半不懂）
煮酒论英雄
直接看题解就好了。写的挺清楚。你甚至不需要 KMP，可以直接 Hash 暴力。想到“将存在包含关系的字符串处理掉”还是挺重要的？？？
namespace liuzimingc {
#define endl '\n'
#define ull unsigned long long
const int N = 20, M = 2e4 + 5, P = 13331, INF = 1e18;int n, len[N], a[N], tot, mx[N][N][2][2], f[1 << 16][N][2], sum, ans; // not hard to "design"!
pair<int, int> broke_my_promise[N];
char s[N][M];
ull p[M], hash[N][M][2];
bool vis[N];ull get(int i, int l, int r, int typ) {return hash[i][r][typ] - hash[i][l - 1][typ] * p[r - l + 1];
}bool check(int x, int y) { // check if s[y] is a subcheese of s[x]if (len[y] > len[x]) return false;for (int i = 1; i + len[y] - 1 <= len[x]; i++)if (get(y, 1, len[y], 0) == get(x, i, i + len[y] - 1, 0)) return true;for (int i = 1; i + len[y] - 1 <= len[x]; i++)if (get(y, 1, len[y], 1) == get(x, i, i + len[y] - 1, 0)) return true;return false;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >> n;p[0] = 1;for (int i = 1; i <= 2e4; i++) p[i] = p[i - 1] * P; for (int i = 1; i <= n; i++) {cin >> (s[i] + 1);broke_my_promise[i] = make_pair(len[i], i);len[i] = strlen(s[i] + 1);for (int j = 1; j <= len[i]; j++) hash[i][j][0] = hash[i][j - 1][0] * P + s[i][j]; // B / G -> 0 / 1?for (int j = 1; j <= len[i]; j++) hash[i][j][1] = hash[i][j - 1][1] * P + s[i][len[i] - j + 1]; // B / G -> 0 / 1?}sort(broke_my_promise + 1, broke_my_promise + 1 + n);for (int i = 1; i <= n; i++) {if (vis[i]) continue;for (int j = i + 1; j <= n; j++)vis[broke_my_promise[j].second] |= check(broke_my_promise[i].second, broke_my_promise[j].second);// my promise broken in the end...}for (int i = 1; i <= n; i++)if (!vis[i]) a[++tot] = i, sum += len[i]; // not a subcheesefor (int i = 1; i <= tot; i++)for (int j = 1; j <= tot; j++)for (int k = 0; k <= 1; k++)for (int l = 0; l <= 1; l++) {// i's end j's start for (int t = 1; t < min(len[a[i]], len[a[j]]); t++)if (get(a[i], len[a[i]] - t + 1, len[a[i]], k) == get(a[j], 1, t, l)) mx[i][j][k][l] = t;}// sum - ans...memset(f, -0x3f, sizeof(f));f[1][0][0] = 0;for (int i = 1; i < 1 << tot; i++) {for (int j = 0; j < tot; j++) { if (!(i >> j & 1)) continue;for (int k = 0; k < tot; k++) {if (i >> k & 1) continue;for (int l = 0; l <= 1; l++)for (int t = 0; t <= 1; t++)f[i | (1 << k)][k][l] = max(f[i | (1 << k)][k][l], f[i][j][t] + mx[j + 1][k + 1][t][l]);}} }for (int i = 0; i < tot; i++) {ans = max(ans, f[(1 << tot) - 1][i][0] + mx[i + 1][1][0][0]);ans = max(ans, f[(1 << tot) - 1][i][1] + mx[i + 1][1][1][0]);}cout << max(2, sum - ans) << endl;return 0;
}
#undef int
} // namespace liuzimingc
威震逍遥津
爆搜稳定 AC。谁还写 dp 啊。当然经统计还是有三个人的。
多剪剪枝：
namespace liuzimingc {
const int N = 1e2 + 5, INF = 1e18;
#define endl '\n'int n, l, st, sum[N];
bool flag = true;
vector<pair<string, int>> e[300];
map<string, bool> vis;
string ans = "-";void dfs(string s) { // number of lowercases, can be calculated easilyif (vis[s]) return;if (islower(s[0]) && ans != "-") {if (s[0] > ans[0]) return;if (s[0] == ans[0] && s[1] > ans[1]) return;}if (1.0 * (clock() - st) / CLOCKS_PER_SEC > 0.75) return;int x = 0;for (int i = 0; i < s.length(); i++)if (islower(s[i]) || !sum[s[i]]) x++;if (l && x > l) return;vis[s] = true;bool flag = true;for (int i = 0; i < s.length(); i++)if (isupper(s[i])) {flag = false;for (const auto &j : e[s[i]])dfs(s.substr(0, i) + j.first + s.substr(i + 1));}if (flag && s.length() == l) {if (ans == "-") ans = s;else ans = min(ans, s);}
}int get_lower(string s) {int sum = 0;for (int i = 0; i < s.length(); i++)if (islower(s[i])) sum++;return sum;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);srand(490522);cin >> n >> l;st = clock();for (int i = 1; i <= n; i++) {string s;cin >> s;if (s.length() == 2) sum[s[0]] = 1;e[s[0]].push_back(make_pair(s.substr(2), get_lower(s.substr(2))));}for (int i = 'A'; i <= 'Z'; i++)random_shuffle(e[i].begin(), e[i].end());sort(e['A'].begin(), e['A'].end());dfs("S");cout << ans << endl;return 0;
}
} // namespace liuzimingc
至于 dp 定义是神。感觉写了我也不一定会。重要的是：
实际上也可以有更粗暴的转移方法，将朴素的 dp 跑若干遍即可，正确性的证明可以考虑转移边和状态实际上构成图，转移的过程就是跑最短路，上述的过程可以看成是 SPFA 算法。
很厉害，多跑几遍就行了？？？和某场牛客的 dp 挺像的。
