DP на DAG
Многие задачи динамического программирования можно представить в виде ориентированного ациклического графа (DAG).
В динамическом программировании задача разбивается на подзадачи.
Каждая подзадача соответствует состоянию.
В DAG:
Если из состояния можно перейти в состояние , то в DAG есть ребро:
В DP переходы не должны образовывать циклы:
Поэтому граф состояний — ациклический.
Дан ориентированный ациклический граф.
Найти длину самого длинного пути.
Пусть:
Тогда для каждого ребра:
имеем переход:
База:
Ответ:
Дан ориентированный граф с вершинами и рёбрами.
Каждой вершине сопоставлена строчная латинская буква.
Значение пути — максимальное число вхождений одной и той же буквы на этом пути.
Пример:
abaca → значение (буква a)
Требуется найти путь с максимальным значением.
Если в графе есть цикл, ответ считается бесконечным → вывести .
Если граф ациклический, можно сделать DP по DAG.
Пусть:
где:
Для ребра:
обновляем:
Используем топологическую сортировку (Kahn):
Если обработано < вершин → есть цикл.
const int MAXN = 100005;
int dp[MAXN];
int longestPathFromNode(int v, const vector<vector<int>>& g) {
if (dp[v] != -1) return dp[v];
dp[v] = 1;
for (int u : g[v]) {
dp[v] = max(dp[v], 1 + longestPathFromNode(u, g));
}
return dp[v];
}
int longestPath(int N, const vector<vector<int>>& g) {
memset(dp, -1, sizeof(dp));
int ans = 0;
for (int v = 1; v <= N; v++) {
ans = max(ans, longestPathFromNode(v, g));
}
return ans;
}
int solve(int n, vector<vector<int>>& edges, string s) {
vector<int> deg(n + 1);
vector<vector<int>> g(n + 1);
// построение графа
for (int v = 1; v <= n; v++) {
for (int u : edges[v]) {
g[v].push_back(u);
deg[u]++;
}
}
vector<vector<int>> f(n + 1, vector<int>(26, 0));
queue<int> q;
// стартовые вершины
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
f[i][s[i-1] - 'a'] = 1;
}
}
int cnt = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
cnt++;
for (int u : g[v]) {
for (int c = 0; c < 26; c++) {
f[u][c] = max(
f[u][c],
f[v][c] + (c == s[u-1] - 'a')
);
}
deg[u]--;
if (deg[u] == 0)
q.push(u);
}
}
if (cnt != n)
return -1;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int c = 0; c < 26; c++) {
ans = max(ans, f[i][c]);
}
}
return ans;
}