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;
}