Tính số cách đi qua cầu

#1

Cho một chiếc cầu ngang có chiều dài N+1 được tạo bởi các ô vuông kích thước 1×1 được đánh số từ 0 đến N, bạn đứng tại vị trí 0 lúc bắt đầu, và một chiếc giầy đăc biệt có thể nhảy xa tối đa M ô, tối thiểu 1 ô.

Yêu cầu: Bạn hãy chỉ ra có bao nhiêu cách có thể đi đến vị trí thứ N của cây cầu này với đôi giầy đặc biệt kia. Được biết trên cây cầu có K vị tri bị hỏng và bạn không thể bước vào đó.

Input:

  • Dòng đầu tiên chứa 3 số N, M, K.
  • Dòng 2 chứa K số là vị trí các ô bị hỏng.

Output: Gồm 1 dòng chứa số cách đi qua cầu mod 1000000007.

vd:

input output
8 3 2
3 4		 8
#2

Nếu thế thì mình dùng các tính Sum là tổng số các qua cầu ở trường hợp cầu không bị hỏng
Exception là số cách qua cầu mà khi đó có dùng đến ô bị hỏng
Result = Sum - Exception
Ổn không?

#3

Thế cậu định tính phần exception kiểu gì?

#4

Bài này tương tự bài này

Gọi f[x] là số cách đi đến vị trí x.

Bạn thử suy nghĩ xem

if (vị trí x hỏng)
    f[x] = ?
else
    f[x] phụ thuộc vào cái gì? từ vị trí y nào đó nhảy đến x như thế nào?
2 Likes
#5

Dynamic programming
Gãy => f[i] = 0
Không gãy => F[i] = tổng số cách đi tới i = tổng số cách đi tới i-1,i-2,…i-m = f[i-1] + f[i-2] +… + f[i-m]

4 Likes
#6

Bạn vui lòng thêm spoil tag vào nhé :smiley:

2 Likes
#7

Bổ sung là nếu i-m =0 thì có nghĩa là có thể tự đi từ 0 đến bước i nên f[i] phải + 1 mới đầy đủ trường hợp.

#8

Đây là source code của mình viết bằng C++14 theo style mì ăn liền của CP. Các bạn có thể tham khảo xem thử và kiểm tra lại nếu thấy không ổn. https://ideone.com/YXbGgM

1 Like
#9

Circular buffer O(M) mem :slight_smile:

buff

Đếm số cách đi hết cầu thang

3 Likes
#10

thật ra thì nếu muốn bổ sung thì vẫn còn cái để bổ sung nữa, nói chung là mình góp idea là chính, còn những vấn đề nhỏ nhỏ xung quanh idea đó thì để người làm bài tự mà giải quyết thôi.
Ví dụ như công thức trên của mình O(N*M) cũng bị tạch thôi
bài này chỉ giải O(N) mới pass được, chuyện tối ưu nó thì tùy thuộc vào độ nhạy bén của bạn ấy mà thôi
f[i] = f[i-1]*2 - f[i-m-1]

2 Likes
#11

bạn thật sự nghĩ công thức trên có thể pass được full testcase sao mà cần phải che giấu

2 Likes
#12

Mình muốn bạn thớt suy nghĩ và trả lời, chứ không phải 1 câu trả lời quá dễ dàng từ 1 người khác khiến bạn ấy không cần suy nghĩ.

3 Likes
#13 
long a[n+1];
long ans[n+1];

Quá không ổn. Chưa kể khai báo mảng trong stack có nguy cơ bị tràn stack.

2 Likes
#14

thật ra thì trông tình hình thì chắc chỉ có chúng ta tự thảo luận với nhau thôi, với lại comment công thức đó không đủ để pass hết testcase được :smile:

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?