Bài viết này sẽ tập trung vào việc giải quyết các bài toán liên quan đến cấu trúc cây và chuỗi thông qua các kỹ thuật lập trình động. Chúng ta sẽ phân tích một số vấn đề cụ thể, cải tiến mã nguồn để tăng tính dễ hiểu và hiệu quả.
T1: Tìm giá trị cực đại và cực tiểu trong cây
Trong bài toán này, chúng ta cần tìm các giá trị lớn nhất và nhỏ nhất trong mỗi nhánh của cây bằng cách sử dụng cấu trúc dữ liệu liên kết (Union-Find).
Xem mã nguồn
<?php
define('MAXN', 100005);
$head = array_fill(0, MAXN, 0);
$next = array_fill(0, MAXN * 2, 0);
$to = array_fill(0, MAXN * 2, 0);
$cnt = 0;
function add($x, $y) {
global $head, $next, $to, $cnt;
$cnt++;
$next[$cnt] = $head[$x];
$to[$cnt] = $y;
$head[$x] = $cnt;
}
$f = array_fill(0, MAXN, 0);
$mx = array_fill(0, MAXN, 0);
$mn = array_fill(0, MAXN, PHP_INT_MAX);
$siz = array_fill(0, MAXN, 0);
function find($x) {
global $f;
return $x == $f[$x] ? $x : $f[$x] = find($f[$x]);
}
function dfs($u) {
global $head, $next, $to, $mx, $mn, $siz, $ans;
$mx[$u] = $mn[$u] = $u;
$siz[$u] = 1;
for ($i = $head[$u]; $i; $i = $next[$i]) {
$v = $to[$i];
dfs($v);
$siz[$u] += $siz[$v];
$mx[$u] = max($mx[$u], $mx[$v]);
$mn[$u] = min($mn[$u], $mn[$v]);
}
if ($mx[$u] - $mn[$u] + 1 == $siz[$u]) $ans++;
}
$n = intval(trim(fgets(STDIN)));
for ($i = 1; $i <= $n; $i++) $f[$i] = $i;
for ($i = 1; $i < $n; $i++) {
list($a, $b) = explode(" ", trim(fgets(STDIN)));
add($a, $b);
$x = find($a);
$y = find($b);
if ($x != $y) $f[$y] = $x;
}
$rt = find(1);
dfs($rt);
echo $ans . "\n";
?>
T2: Lập trình động với điều kiện tăng giảm
Vấn đề này yêu cầu chúng ta tính số lượng cách sắp xếp một chuỗi ký tự sao cho thỏa mãn điều kiện tăng hoặc giảm tại các vị trí xác định.
Xem mã nguồn
#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
string s;
while (cin >> s) {
int n = s.size() + 1;
s = " " + s;
long long dp[n+1][n+1], sum[n+1][n+1];
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; ++i) { dp[1][i] = sum[1][i] = 1; }
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j) {
if (s[i] == 'I') dp[i][j] = (sum[i-1][j-1] + dp[i][j]) % MOD;
else if (s[i] == 'D') dp[i][j] = ((sum[i-1][i-1] - sum[i-1][j-1] + MOD) % MOD + dp[i][j]) % MOD;
else dp[i][j] = (sum[i-1][i-1] + dp[i][j]) % MOD;
sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
}
long long ans = 0;
for (int i = 1; i <= n; ++i) ans = (ans + dp[n][i]) % MOD;
cout << ans << '\n';
}
return 0;
}
T3: Tính số lượng dãy con chung dài nhất
Bài toán cuối cùng liên quan đến việc tính số lượng dãy con chung dài nhất giữa hai chuỗi, sử dụng phương pháp lập trình động nâng cao.
Xem mã nguồn
#include <iostream>
#include <string>
using namespace std;
const int N = 1005, MOD = 1e9 + 7;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
string sa, tb;
cin >> sa >> tb;
int n = sa.size(), m = tb.size();
int a[N], b[N], dp[N][N], p[26][N];
int dp2[N][N];
memset(p, -1, sizeof(p));
for (int i = 1; i <= n; ++i) a[i] = sa[i-1] - 'a';
for (int i = 1; i <= m; ++i) b[i] = tb[i-1] - 'a';
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
}
for (int i = 1; i <= m; ++i) {
p[b[i]][i] = i;
for (int j = 0; j < 26; ++j) p[j][i] = max(p[j][i], p[j][i-1]);
}
for (int i = 0; i <= n; ++i) dp2[i][0] = 1;
for (int i = 0; i <= m; ++i) dp2[0][i] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
dp2[i][j] = 0;
if (dp[i][j] == dp[i-1][j]) dp2[i][j] = (dp2[i][j] + dp2[i-1][j]) % MOD;
int pos = p[a[i]][j];
if (pos != -1 && dp[i][j] == dp[i-1][pos-1] + 1) dp2[i][j] = (dp2[i][j] + dp2[i-1][pos-1]) % MOD;
}
cout << dp2[n][m];
return 0;
}