# A5 ôn bài (series)

---
# BFS

## Labyrinth
Dùng BFS nhưng:
- trên lưới
- truy vết: lưu lại hướng đi tới ô $(x,y)$ bất kì.

## Monsters
BFS đa nguồn
Tính khoảng cách ngắn nhất từ 1 quái vật tới ô $(x,y)$ bất kì, gọi là $d(x,y)$.
Tìm chiến thuật cho người: Muốn đi tới ô $(x,y)$ vào thời điểm $i$ thì phải có $i < d(x,y)$ (tới sớm hơn hẳn)

### Sol 2
Đạt, Hiếu orz
Vừa đi vừa đánh dấu bảng.
Thêm toàn bộ quái vật vào queue, sau đó thêm người vào.
Trong quá trình BFS, ta gán kí tự ở ô $(u,v)$ kề $(x,y)$ bằng chính kí tự ở ô $(x,y)$ (mô phỏng lại "bước đi" của người / quái vật)

## NUMK
### Trâu
### Full
Coi mỗi số là một đỉnh (chỉ quan tâm số dư cho $M$).
Từ một số $x$, chia $M$ dư $r$, thêm một chữ số $d_i$ vào sau nó thì được: số $10x + d_i$, chia $M$ dư $(10r + d_i) \mod M$
Ta ưu tiên thêm chữ số bé trước chữ số lớn.
Dùng BFS tìm đường đi ngắn nhất từ các đỉnh ban đầu (số có 1 chữ số), đi tới đỉnh $0$

#### Chứng minh
Thuật trên sẽ ưu tiên số có số lượng chữ số ít hơn.
Trong những số cùng chữ số, do ta đã ưu tiên chọn chữ số **bé** hơn trước, nên sẽ được số nhỏ hơn.

---
# DP
## CHIADAY
sub 2: cố định x1,x2 xong
x3 chính là vị trí để Sum(x3,n+1) đạt min

QHĐ: Thấy được cần chia mảng thành 4 phần
Đặt $dp(i,j):$ xét $i$ phần tử đầu, đang ở phần thứ $j$ thì tổng $\max =?$

## POKEMON
sub 1: duyệt n! hoán vị
sub 3:
Đặt dp(mask, i): tập hợp loại pokemon đã thu phục là số mask,
con cuối cùng thu phục là i
Có $2^m * n$ trạng thái.

Công thức:
từ $dp(mask,i)$ cập nhật cho $\texttt{dp(mask | (1<<t[j]), j)}$

ĐPT: $O(2^m \cdot n^2)$

## cses1686
Lưu ý: mỗi ô chỉ tính vào tổng 1 lần.
Dùng tarjan, nén các TPLT mạnh về thành 1 đỉnh. Đồ thị mới tạo được sẽ là DAG.
Đặt $f(u)$: Tổng lớn nhất của đường đi bắt đầu/ kết thúc tại đỉnh $u$