DAGda DP
Dinamik dasturlashning ko‘plab masalalarini yo‘naltirilgan asiklik graf (DAG - directed acyclic graph) ko‘rinishida tasvirlash mumkin.
Dinamik dasturlashda masala kichik masalalarga bo‘linadi.
Har bir kichik masala holatga mos keladi.
DAGda:
Agar holatidan holatiga o‘tish mumkin bo‘lsa, u holda DAGda qirra mavjud:
DPda o‘tishlar sikllar hosil qilmasligi kerak:
Shuning uchun holatlar grafigi — asiklik.
Yo‘naltirilgan asiklik graf berilgan.
Eng uzun yo‘l uzunligini toping.
Quyidagicha belgilaymiz:
Unda har bir qirra uchun:
o‘tish:
Baza:
Javob:
ta cho‘qqi va ta qirrali yo‘naltirilgan graf berilgan.
Har bir cho‘qqiga kichik lotin harfi mos qo‘yilgan.
Yo‘l qiymati — shu yo‘lda bir xil harfning uchrashishlarining maksimal soni.
Misol:
abaca → qiymat (a harfi)
Maksimal qiymatli yo‘lni topish talab etiladi.
Agar grafda sikl bo‘lsa, javob cheksiz deb hisoblanadi → chiqarish.
Agar graf asiklik bo‘lsa, DAG bo‘yicha DP qilish mumkin.
Quyidagicha belgilaymiz:
bu yerda:
Qirra uchun:
yangilaymiz:
Topologik saralashdan (Kahn) foydalanamiz:
Agar qayta ishlangan cho‘qqilar < bo‘lsa → sikl bor.
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;
}