không thể hiểu được một giải pháp dp

Question

Vấn đề là như sau:

Lazer Tag bao gồm một vở kịch nhóm, nơi bạn được giao một số cố định của đạn (thường được gọi là bức ảnh Laser) trong toàn bộ trò chơi . Mỗi lần bắn vào kẻ thù mục tiêu của bạn, sẽ cho bạn một điểm.

Cân nhắc chuỗi lượt truy cập và lần bỏ lỡ của bạn có thể được biểu diễn dưới dạng "x" và "o" trong đó "o" biểu thị lần truy cập và "x" biểu thị một lần bỏ lỡ. Giả sử chuỗi có dạng “xxxoooxxxxooxxo”, thì điểm số cuối cùng của bạn sẽ bằng 3^2 + 2^2 +1^2 tôi thêm các ô vuông của mỗi số lần truy cập liên tiếp tối đa trong toàn bộ lần chơi trò chơi.

Xác suất nhấn cú đánh chính xác (1≤j≤n) là P (j). Nói một cách đơn giản, xác suất nhận được “o” trong chuỗi tại lần lượt thứ j là P (j). Bạn cần tính điểm số mong đợi ở cuối vòng của bạn.

Tôi có thể hiểu giải pháp O (n^2) của việc này bằng cách ghi nhớ nhưng câu hỏi yêu cầu giải pháp O (n). Tôi đã thấy giải pháp O (n) nhưng tôi không thể hiểu được nó. Giải pháp O (n) là như sau:

for(i = 1; i <= n; i++) 
    dp[i] = (dp[i-1] + p[i-1]) * p[i]; 
for(i = 1; i <= n; i++) 
    ans+=2 * dp[i] + p[i]; 

trong đó p [i] là đích xác đạt mục tiêu thứ i. Bất cứ ai có thể giải thích làm thế nào O (n) giải pháp hoạt động?

Answer 1

Bạn có thể nghĩ đến các điểm theo cách sau:

1. 1 điểm cho mỗi nhấn
2. 2 điểm cho MỌI chạy của hit chiều dài> 1 (điểm chồng chéo chạy nhiều lần)

Ví dụ, một chuỗi các xxooox sẽ điểm:

1. +1 cho mỗi o của
2. 2 cho ooo
3. 2 cho oo đầu tiên
4. 2 cho oo thứ hai

Điểm = 3 + 1 * 2 * 3 = 3 + 6 = 9 điểm. (Điều này phù hợp với cách ban đầu của điểm số vì 9 = 3 * 3)

dp [i] tính toán số lần chạy dự kiến ​​có thời lượng> 1 kết thúc tại vị trí i.

Vì vậy, để tính tổng số điểm dự kiến, chúng tôi cần tổng 2 * dp [i] (khi chúng tôi nhận được 2 điểm cho mỗi lần chạy), cộng với tổng p [i] để thêm điểm số dự kiến ​​từ nhận 1 điểm cho mỗi lần truy cập.

Mối quan hệ tái phát là vì số lượng dự kiến ​​của chạy chiều dài> 1 kết thúc ở vị trí i sẽ là:

1. +1 nếu chúng ta có một hoạt động mới bắt đầu từ vị trí i bằng cách nhận một hit tại i và i-1 (xác suất p [i] * p [i-1])
2. + dp [i-1] nếu chúng tôi tiếp tục chạy kết thúc tại vị trí i-1 bằng cách nhận lần truy cập khác (xác suất p [i])