Codeforces - 1415C - Bouncing Ball

★ Today's tune: https://youtu.be/Oj18EikZMuU

★ Link: https://codeforces.com/contest/1415/problem/C

★ Tags: dp

★ Difficulty: 1400

★ Ý tưởng:

Bài này thuần dp. Công thức quy hoạch động như sau:

Khi đang ở một vị trí i (i >= p, vì bóng được ném p đơn vị trước khi nảy), ta sẽ có 2 cách chọn: i là điểm bóng được ném tới, hoặc i là điểm bóng bị nảy tới.

• Nếu chọn i là điểm được ném tới, ta sẽ phải bỏ đi các vị trí từ 1 đến i - p, và nếu tại vị trí i chưa được xây sẵn thì ta phải xây thêm: dp[i] = min(dp[i], (i - p) * y + (s[i]=='1' ? 0 : x))
• Nếu chọn i là điểm nảy, suy ra điểm trước khi bóng nảy tới i sẽ là i - k, và nếu tại vị trí i chưa được xây sẵn thì ta phải xây thêm: dp[i] = min(dp[i], dp[i - k] + (s[i]=='1' ? 0 : x))

★ Code: https://ideone.com/jQac9B