Robot Dò Tìm Địa Chất Trên Sườn Núi

Buổi 51 — Probability DP Dynamic Programming
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một robot tự hành khảo sát địa chất trên sườn núi chia thành lưới $R \times C$ ô, xuất phát từ ô $(1, 1)$ và hướng tới trạm thu hồi tại ô $(R, C)$. Tại mỗi ô $(i, j)$, robot thu được mẫu khoáng sản có giá trị $V_{i,j}$. Nếu đang ở hàng cuối $R$, robot bắt buộc đi sang phải $(i, j+1)$; nếu đang ở cột cuối $C$, robot bắt buộc đi xuống dưới $(i+1, j)$. Tại các ô còn lại, robot chọn đi sang phải với xác suất $P_{i,j} / 100$ và đi xuống dưới với xác suất $(100 - P_{i,j}) / 100$. Hãy tính kỳ vọng tổng giá trị khoáng sản thu được trên hành trình từ $(1, 1)$ đến $(R, C)$ theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng 1 gồm hai số nguyên $R, C$ ($1 \le R, C \le 300$). $R$ dòng tiếp theo, mỗi dòng gồm $C$ số nguyên $V_{i,j}$ ($0 \le V_{i,j} \le 10^6$). $R$ dòng tiếp theo, mỗi dòng gồm $C$ số nguyên $P_{i,j}$ ($0 \le P_{i,j} \le 100$).

Dữ liệu ra

In ra kỳ vọng tổng giá trị khoáng sản theo modulo $10^9 + 7$.

Ví dụ
Input Output
2 2
1 2
3 4
50 0
0 0
500000011
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved