Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"tqnnoname","updateTime":1702021006000,"title":"DƠI BAY TRONG ĐÊM","dislikeCnt":0,"content":"Đề bài: [https://vjudge.net/contest/598440#problem/F](http://)\nMột cách giải phổ biến cho bài này: Sử dụng quy hoạch động 1 chiều kiểu ngược.\nGọi dp[i] là lượng sức nhỏ nhất mà chú dơi cần sử dụng để bay từ cây đang đậu đến cây thứ i. Khi đó, đáp án của bài toán chắc chắn là dp[n].\n- Các bạn có thể thấy: Mỗi lần bay chỉ được đậu đến cây số i + 1 hoặc cây i + 2, vậy nếu từ tương lai nhìn về quá khứ, nếu giờ đứng ở vị trí thứ i thì chắc chắn ban đầu đã từng đứng ở cây i - 1 hoặc i - 2. Do đó, muốn tính lượng sức đến cây thứ i, ta chỉ cần tính lượng sức bay đến cây i - 1 hoặc i - 2 cộng với lượng sức từ cây thứ i -1 hoặc i - 2 đến i. Do đó, công thức sinh ra là:\n`dp[i] \u003d dp[i - 1] + abs(h[i] - h[i - 1])` hoặc \n`dp[i] \u003d dp[i - 2] + abs(h[i] - h[i - 2]).`\nChú ý thêm, ta cần tìm để lượng sức là nhỏ nhất khi đến cây thứ i, do đó:\n`dp[i] \u003d min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]).`\nNhưng vấn đề đặt ra, i chỉ có thể nhỏ nhất chạy từ 3 nếu sử dụng công thức trên. Do đó, ta cần tìm dp[1] hoặc dp[2] để giải quyết bài toán. Đó chính là trường hợp gốc (trường hợp cơ sở) để giải bài toán này.\n- Giờ ta cần tìm trạng thái cơ sở cho bài toán. Chắc chắn rằng, nếu ban đầu ta đứng ở đâu thì chắc chắn ta chẳng tốn sức để bay đến đó. Do đó, `dp[1] \u003d 0`\nBên cạnh đó, nếu ta từ vị trí cây ban đầu bay đến cây thứ nhất thì chỉ có 1 cách duy nhất nên lượng sức cũng là duy nhất. Do đó: `dp[2] \u003d abs(h[2] - h[1])`.\n\u003cp\u003e Các trường hợp khác, ta dùng theo công thức chuyển trạng thái của quy hoạch động như đã viết ở trên. Độ phức tạp của bài toán nếu giải theo phương pháp trên là O(n). Chúc các bạn may mắn.\u003c/p\u003e","threadId":177773,"likeCnt":0,"createTime":1702014777000,"isWorkbook":false,"viewCnt":165,"openness":2,"fav":false,"id":4360,"trustable":false}