# HD HSG 11 BDH 21

[Nhận xét đề thi](https://hackmd.io/gnOHw_IVSIysTTtRN0MdkA)

## Bài 1:
Dùng priority_queue: lấy ra 2 số nhỏ nhất, cộng lại rồi add kết quả vào lại. Lặp lại cho đến khi còn 1 phần tử

## Bài 2:
Hàm F(N) như sau:
* Nếu N<=9 thì trả về 1;
* Nếu N=1000 thì trả về 1000;
* a=N/100; b = N%100/10; c= N%10;
* Nếu N<=99 thì
* Nếu b=c thì trả về 11
* Ngược lại, trả về 10;
* Nếu a=b=c thì trả về 111;
* Nếu a=b≠c thì trả về 110;
* Nếu a≠b=c thì trả về 100;
* Nếu a=c≠b thì trả về 101;
* Trả về 102

## Bài 3
Làm như mô tả: tích các chữ số tối đa 9^9. Tổng các chữ số tối đa 81.
Có thể dùng quy hoạch động chữ số.

## Bài 4:
Quy hoạch động
Gọi F[i] là tổng tiền nhỏ nhất để thuê bảo vệ từ thời điểm 0 đến i (i=0..n). Ban đầu F[i]= ∞ hết, riêng F[0]=0;
Sort tăng dần theo thời điểm bắt đầu
Với mỗi vệ sĩ i: F[j]=min(F[j],F[si]+ci), j=si+1..ti;
Đáp án F[n]

Hướng 2:
Sort vệ sĩ tăng dần theo thời điểm kết thúc (ti)
Gọi F[i] là tổng tiền nhỏ nhất để thuê bảo vệ từ thời điểm 0 đến thời điểm mà người vệ sĩ i kết thúc canh gác (i=1..m).

F[0]=0;
Với mỗi i chạy từ 1 đến m:
* Nếu s[i] = 0 thì F[i]=c[i], ngược lại F[i]=∞;

Với mỗi i chạy từ 1 đến m:
* Tìm j nhỏ nhất mà t[j] ≥ s[i]; (1)
* Nếu không có j thì tiếp tục vòng lặp;
* F[i] = c[i]+min(F[j..i-1]) (2)

Viết F[m];

Ghi chú:
(1) có thể dùng TKNP;
(2) tìm min trên đoạn;