[Cây IT] [AMPPZ] [SPOJ] POSTERS

Đề bài
Hướng làm
Rời rạc hóa tọa độ các tấm poster (tức là biến đổi tọa độ các tấm poster sao cho tọa độ lớn thứ i sẽ có giá trị i). Sau đó ta dùng cây IT, với mỗi nút lưu số thứ tự tấm poster cuối cùng bao trùm cả đoạn đó. Tấm poster cuối cùng bao trùm một điểm là tấm poster có số thứ tự lớn nhất của các nút chứa đoạn nằm trên điểm đó.
Code

[DFS và BFS] [SPOJ] POUR1

Đề bài
Hướng làm
BFS theo từng trạng thái của hai bình, khi BFS đánh dấu lại số thao tác để in ra khi cần, cũng như tránh xét một thao tác nhiều lần.
Code

[Quy hoạch động] [SPOJ] LQDGONME

Đề bài
Hướng làm (có tham khảo bên traitaodo)
Code

[Quy hoạch động] [SPOJ] COUNTPL

Đề bài
Hướng làm
Bước 1:
Tham khảo Nguyễn Hoành Tiến, đã sửa lại cho đúng
Dùng mảng F[i, j] có ý nghĩa: F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j của S có/không là palindrome.
Ta có công thức là:
F[i, i] = True
F[i, j] = (F[i+1, j-1] or (j-i=1)) ( nếu S_i = S_j )
F[i, j] = False; ( nếu S_i <> S_j )
Bước 2:
Gọi dp[i] là kết quả nếu chỉ xét xâu s[1..i].
Ta có dp[i]=dp[j-1]+1 với dp[j-1] nhỏ nhất và thỏa mãn j<=i và f[j,i] (giống bài NKREZ)
Code

[Chưa hoàn thiện] [Quy hoạch động] [VM] [SPOJ] LSFIGHT

Đề bài
Ta chuẩn hóa lại dữ liệu như sau:
Nếu i thắng k và k thắng j thì i có thể thắng j.
Sau đó đếm số người có khả năng thắng tất cả những người còn lại.
Code (96 điểm SPOJ)
Vẫn tiếp tục nghĩ...

[Quy hoạch động] [SPOJ] DTDOI

Đề bài
Dễ có công thức truy hồi
f[i] = min(f[i],f[i-a[j]]+1) với i là số tiền cần đổi, khởi tạo f[i]=oo (dương vô cùng).
Tuy vậy, do s quá lớn nên ta tham bằng cách đổi gần hết s bằng mệnh giá lớn nhất, sau đó quy hoạch động phần tiền thừa còn lại.
Code

[Quy hoạch động] [COI] [SPOJ] MBLAST

Đề bài
Hướng làm (có tham khảo bên traitaodo)
Lưu ý: Test có thể có dấu cách cuối 2 xâu nên ta phải xử lí.
Code

[Quy hoạch động] [SPOJ] NKREZ

Đề bài
Hướng làm
Sắp xếp lại các yêu cầu theo thời điểm đầu.
Gọi f[i] là thời gian lớn nhất hội trường sử dụng khi chỉ nhận yêu cầu i và các yêu cầu trước đó, sử dụng hai vòng lặp lồng nhau (xem bài COUNTPL) ta dễ dàng tìm được f[i].
Kết quả là max(f[1..n]).
Code

[Quy hoạch động] [VM] [SPOJ] VSTEPS

Đề bài
Hướng làm
Tạo mảng boolean l đánh dấu các bậc thang bị lủng.
Theo quy tắc cộng, dễ có công thức truy hồi
f[i]=0 nếu bậc i bị lủng
f[i]=f[i-1]+f[i-2] nếu bậc i không bị lủng.
Code

[Quy hoạch động] [SPOJ] C11KM

Đề bài
Hướng làm (có tham khảo của onlylove97, đã sửa lại cho đúng)
Gọi f[i] là tổng số phiếu có thể có khi tới ngày thứ i, d[i][j] là chi phí nhỏ nhất khi mua tới mặt hàng thứ i, còn j phiếu
->d[i][j]=min

1. d[i-1][j]+p[i] (không sử dụng phiếu mua hàng, điều kiện j<=f[i-1])
2. d[i-1][j-1]+p[i] (có thêm một phiếu, điều kiện p[i]>100 và j>0)
3. d[i-1][j+1] (sử dụng phiếu mua hàng,điều kiện j<f[i-1]).

kết quả min(d[n][ 0.. f[n] ]).
Code

[Quy hoạch động] [SPOJ] C11CAVE

Đề bài
Hướng làm:
B1: Xây dựng mảng a
- Với mỗi măng đá, tăng a[i] lên 1 với i là độ cao điểm đầu của măng đá (tính từ dưới đất) và giảm a[j+1] xuống 1 với j là độ cao điểm cuối măng đá (cũng tính từ dưới đất).
B2: Cộng dồn lại (cách cộng dồn bạn từ nghĩ hoặc xem code, mẹo này mình tham khảo của Triệu Mẫn ở một bài khác) để a[i] trở thành số măng đá đi qua mức i.
B3: Tìm những gì đề bài yêu cầu (có thể kết hợp vào B2).
Lưu ý mảng a khai báo rộng ra một chút để tránh tràn.
Bài này mình tự nghĩ :)
Code

[Quy hoạch động] [SPOJ] AMSSEQ

Đề bài
Hướng làm:
Gọi f[i] là số điểm lớn nhất có thể khi tới ô i.
f[0]=0; f[1]=max(0,a[i]);
Khởi tạo f[i]=10^(-9), sau đó tính f[i]=max(f[i],f[j]+a[i]) với i chạy từ 2 cho đến n, j chạy từ i-k đến i-1.
Kết quả là max(f[i]);
Bài này mình có tham khảo bên kienthuc24h
Code

[Quy hoạch động] [USACO] [SPOJ] VCOWFLIX

Đề bài
Hướng làm:
Tạo một mảng chứa các tổng đang có và một mảng truy vết (trace) để tính số con bò để tạo ra tổng ấy.
Code

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] ROBOCON

Đề bài
Hướng làm:
Tưởng bài này giống bài QBAGENTS, tuy vậy do giới hạn quá lớn nên ta không thể dùng mảng 5 chiều để quy hoạch động được.
Cách làm có tham khảo bên onlylove97
Loang lần lượt từng con robot cho để biết tại thời điểm t các con robot có thể ở vị trí nào, nếu có một ô mà cả hai có thể gặp nhau thì dừng loang, in ra t. Lưu ý các ô có thể đi qua đi lại nhiều lần.
Code (90 điểm SPOJ)

[DFS và BFS] [Quy hoạch động] [Mảng 3 chiều] [SPOJ] QBAGENTS

Đề bài
Hướng làm:
Tham khảo vnspoj.blogspot.com
Gọi F[u,v,k]  là thời gian min để người 1 đến u, người 2 đến v và đến lượt người k đi tiếp. Loang từ F[s,t,1], mỗi lượt luân phiên nhau từng người. Ban đầu khởi  tại F[i,j,k] =maxValue. Kết quả là min(F[u,u,1]). (tùy từng cách code là cộng tiếp thời gian luân phiên hay cộng thời gian theo lượt hai người mà F[u,u,1]/2 hay F[u,u,1]).Code

[DFS và BFS] [Tìm kiếm nhị phân] [USACO] [SPOJ] MTWALK

Đề bài
Hướng làm:
Chặt nhị phân kết quả, sau đó DFS thử xem có đi được không.
Tuy vậy việc kiểm tra độ cao chênh lệch của đường đi quá phức tạp, nên với mỗi độ cao nhỏ nhất, ta tìm độ cao lớn nhất tương ứng với kết quả mình đang xét, sau đó tìm đường đi có độ cao nằm giữa khoảng này (phần này mình tham khảo bên kienthuc24h)
Mình không chặt nhị phân trong code do kết quả cứ ra sai.
Code

[DFS và BFS] [USACO] [SPOJ] NKGUARD

Đề bài
Hướng làm:
Tìm các thành phần liên thông có cùng độ cao trong bảng, sau đó kiểm tra xem thành phần liên thông đó có phải là đỉnh đồi hay không bằng cách kiểm tra độ cao của các thành phần liên thông liền kề.
Cách làm này mình có tham khảo blog của traitaodo 
Code

[DFS và BFS] [VOI] [SPOJ] STABLE

Đề bài
Hướng làm:
- Sử dụng mảng a làm ma trận kề để tránh dữ liệu lặp, đồng thời chuyển thành danh sách kề để giảm độ phức tạp của BFS.
- Dùng BFS tìm số đường đi ngắn nhất đến từng đỉnh, nếu tìm được 2 đường đi ngắn nhất thì tăng biến đếm, cộng thêm nhận xét từ test ví dụ: nếu u ổn định mà u nằm trên đường đi ngắn nhất từ s đến v thì v ổn định, ta giải được bài này.
- Do trên SPOJ có thêm vài giới hạn về bộ nhớ nên ta phải dùng con trỏ để giảm bộ nhớ sử dụng, cũng như loại bỏ mảng a ở trên (thay thế bằng hàm found).
Code

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] STNODE

Đề bài
Hướng làm được 83,33 điểm
BFS tìm 1 đường đi ngắn nhất bất kì từ s đến t, sau đó bỏ dần từng đỉnh rồi DFS thử xem có đến được không.
Thuật chuẩn theo đồn đoán trên mạng là dùng luồng, nhưng cách cài đặt rất phức tạp nên ta sẽ cài sau :)
Code

[DFS và BFS] [Tham lam] [vCoder] [SPOJ] V8ORG

Đề bài
Hướng làm:
DFS từng phần tử như sau:
- Duyệt hết tất cả các thành viên "con"
- Nếu số thành viên "con" của nó vẫn lớn hơn k thì bắt giữ thành viên đó, cập nhập lại số "con" của các thành viên chỉ huy thành viên đó.
Chứng minh đã có trong blog của traitaodo
Code