Solutions of Planting flowers

Select solution language

TENJOKE Created at 0 likes

Ta có thể **chặt nhị phân không nhỉ** ? **Nhận xét: độ xấu là x hợp lí thì độ xấu là x + 1 luôn hợp lí ?** **Khỏi cãi vì nếu chỗ đó là hợp lí thì cùng lắm x + 1 lấy luôn cái trường hợp thỏa mãn là x là xong**. **-> Bài toán đưa về là cách chọn tối ưu nhất sao cho cách nhau không quá k** **-> dùng dp để giải quyết bài toán con này, gọi $dp[i]$ là số tiền nhỏ nhất tới vị trí thứ $i$, khúc này dùng **deque** để giải nè (cơ bản). Nếu kết quả cuối cùng $dp[n] ≤ t$ thì thỏa mãn và tìm tới những cái nhỏ hơn còn nếu $dp[n] > t$ thì không thỏa và tìm tới mấy cái to hơn.** Cụ thể hơn, ta có công thức: $$ dp[i] = a[i] + \min_{j = i - k - 1}^{i - 1} dp[j] $$ bài toán con là **tối ưu hoá min trên đoạn tịnh tiến**, xài deque là rất ổn hehe.