Bài này e nghĩ là sinh ra các số sao cho không có số 13. Nhưng đpt khá lớn nên có anh/bạn nào giúp e cải thiện đpt hoặc có thuật toán nào khác không. Cảm ơn.
Forum VNOI đã tạm ngừng hoạt động. Các bạn có thể hỏi bài trên Group Facebook của bọn mình.
Nghĩ theo hướng DP, bài này cơ bản.
Bài này mình qhd kiểu đệ quy:
long long xuli(int pos, bool pre, bool kt)
trong đó pos là vị trí chữ của đang xét số n (tính từ trái sang phải), pre kiểm tra xem chữ số trước nó là phải là 1 hay ko, kt là để xem dãy từ 1->pos-1 = hay đã nhỏ hơn dãy 1->pos-1 của số n rồi
Từ trạng thái này mình sẽ sinh ra trạng thái tiếp theo và lưu vào một mảng để tránh việc tính đi tính lại nhiều lần
Nó dạng như đệ quy có nhớ đúng không? Mình cũng làm như bạn mà không biết sai chỗ nào, mình nói thử xem đúng ý của bạn không: Mình gọi f[pos, pre, kt] là số lượng số cần tìm : nếu kt =true thì mình chạy j :=0 to (số thứ i của n số) rồi cộng dồn vào f[]; Ngược lại nếu kt= false thì chạy từ 0->9 và cộng dồn vào f[];
Chú ý kết quả bài này có thể vượt quá longint =)))))), cẩn thận cái mảng bạn khai báo
À bạn có đọc dc code c++ ko, mình đọc qua bài bạn thì thấy ý tưởng đúng rồi, nhưng khá dài (có lẽ do bạn chưa quen qhd đệ quy hoặc chưa có kn code) nên nếu bạn muốn tham khảo mình sẽ gửi code cho :)
ok, bạn gửi đi. Cảm ơn nhiều :D
Đây lần đầu tiên mình làm bài dạng này. Mong bạn nói rõ hơn tí nữa được không? Mình có thắc mắc:
+ kt=true nghĩa là số đó đã nhỏ hơn n?
+ n là A hay B trong bài toán?
+ Cộng dồn nghĩa là thế nào?
+Cái kt thì theo định nghĩa của từng người thôi.
+Mình đệ quy 2 lần, lần đầu B nên n=length(B). Lần sau là A-1 nên n=lenght(A-1). Kết quả sẽ là đệ quy của B trừ đệ quy A-1;
+Cộng dồn trong đệ quy thì mình hiểu như vầy, không biết đúng không: Đệ quy thì nó như cái cây vậy á, nếu mình đã đi 1 cái nhánh có rồi thì không cần đi nữa, chỉ lấy kết quả thôi. VD như ở trạng thái try(x, y, z) mà f[x, y, z]<>0 (trạng thái này đã đi rồi) thì exit(f[x, y, z]) không cần đi nữa.
cái này mình hiểu rồi, ý là khi for j chạy đó, bạn gọi đệ quy cho nó tính pos+1 đúng không?
gọi hàm F như thế rồi xuất kq thế nào vậy?????
Rồi lúc cho for j chạy thì tính pos+1, mình cộng dồn vào f[x, y, z] rồi cuối cùng exit(f[x, y, z]). Đệ quy là 1 cái function.
cám ơn bạn. ^^