Mọi người cho mình xin ý tưởng bài này với.
Mọi người cho mình xin ý tưởng bài này với.
Bài này là 1 bài khó. Nó khó ở chỗ có khá nhiều hướng QHD, và không phải hướng nào cũng dẫn đến kết quả đúng. Để có cách làm chặt chẽ thì ở các bước phải có chứng minh đầy đủ, nếu không rất dễ ngộ nhận.
Gợi ý:
Thật ra em cũng làm QHĐ theo kiểu đệ quy có nhớ. Nhưng công thức bị vướng ngay chỗ giữ lại chữ C đó ạ.
Công thức của em như sau: gọi F[i,j] là giá trị lớn nhất khi xóa hết đoạn từ i->j. Res= F[1,n];
Xét làm 2 TH:
* Nếu chữ số ở i <> chữ số ở j thì F[i,j] = max( F[i+1,j] + sqr( sl(i) ) , F[i,j-1]+ sqr( sl(j) ) ); { sl(i) là số chữ số giống chữ số ở i liên tục}
* Ngược lại em tham: Giữ lại tất cả các vị trí có chữ số ở i và xóa hết các thằng kia. Em nghĩ chỗ này sai.
Anh thấy đâu có lý do gì để cách tham của em đúng đâu :))
Em trả lời câu hỏi thế này đúng không ạ?
Câu 1: Tại sao không để lại 2 chữ số?
+ Vì nó sẽ bị trùng - tức là ví dụ: để lại 2 chữ số ở i và j thì khi tính đoạn i->k, k->j nào đó thì k lại xét lại, thế sẽ sai.
Câu 2: C có tính chất gì?
Từ câu hỏi 1 thì c sẽ là chữ số ở i hoặc j.
Câu cuối em chưa nghĩ ra. :D
Anh ơi cách của a đpt là bn ạ?
Với cả mọi người cho em hỏi cái cách làm mà mem có tầm 1mb mà time 0.00s thì là ntn ạ em nghĩ mãi k ra.
N^3.
Khi làm bài em đừng có quan tâm đến thời gian chạy. Thuật toán hằng số nhỏ đpt tốt thì tự nhiên nó ra 1MB time 0.00s thôi, có gì lạ đâu
Tại em thấy nếu mà chỉ dùng 1MB chứng tỏ là bộ nhớ là N^2 thì là một cách làm tốt hơn.
Em muốn tìm hiểu thêm cách đấy :v
Cách N^3 vẫn có thể có bộ nhớ là N^2 mà :@)