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 ý:

• Đầu tiên thử hàm f(i, j) = giá trị lớn nhất nếu xóa hoàn toàn đoạn [i, j]. Cái này nghĩ ra thì do cảm giác / kinh nghiệm thôi.
• Với các bài tương tự (nhưng không có việc gộp 2 dãy con lại trong quá trình xóa), thì thường công thức QHD có dạng f(i, j) = min(f(i, k) + f(k+1, j)). Tuy nhiên nếu công thức kiểu như vậy thì không thể giải quyết được việc gộp 2 đoạn.
• Ý tưởng là giả sử khi xóa đoạn [i, j], ta có thể để lại 1 chữ số C đến cuối cùng. (Tại sao lại không để lại 2 chữ số?). Đặt g(i, j, c, x) = giá trị lớn nhất nếu khi xóa đoạn [i, j], ta để lại đúng x chữ số c. Chú ý là cần có chiều x, do đôi khi ta cần xóa vài chữ số c ở giữa, nhưng đến cuối vẫn để lại chữ số c để xóa cuối cùng.
• Như vậy f(i, j) = max( g(i, j, c, x) + x*x ).
• Đến đây thì còn 2 vấn đề:
  • Làm thế nào để tính g(i, j, c, x) hiệu quả?
  • c có tính chất gì?

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.

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 ý:

• Đầu tiên thử hàm f(i, j) = giá trị lớn nhất nếu xóa hoàn toàn đoạn [i, j]. Cái này nghĩ ra thì do cảm giác / kinh nghiệm thôi.
• Với các bài tương tự (nhưng không có việc gộp 2 dãy con lại trong quá trình xóa), thì thường công thức QHD có dạng f(i, j) = min(f(i, k) + f(k+1, j)). Tuy nhiên nếu công thức kiểu như vậy thì không thể giải quyết được việc gộp 2 đoạn.
• Ý tưởng là giả sử khi xóa đoạn [i, j], ta có thể để lại 1 chữ số C đến cuối cùng. (Tại sao lại không để lại 2 chữ số?). Đặt g(i, j, c, x) = giá trị lớn nhất nếu khi xóa đoạn [i, j], ta để lại đúng x chữ số c. Chú ý là cần có chiều x, do đôi khi ta cần xóa vài chữ số c ở giữa, nhưng đến cuối vẫn để lại chữ số c để xóa cuối cùng.
• Như vậy f(i, j) = max( g(i, j, c, x) + x*x ).
• Đến đây thì còn 2 vấn đề:
  • Làm thế nào để tính g(i, j, c, x) hiệu quả?
  • c có tính chất gì?

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 ý:

• Đầu tiên thử hàm f(i, j) = giá trị lớn nhất nếu xóa hoàn toàn đoạn [i, j]. Cái này nghĩ ra thì do cảm giác / kinh nghiệm thôi.
• Với các bài tương tự (nhưng không có việc gộp 2 dãy con lại trong quá trình xóa), thì thường công thức QHD có dạng f(i, j) = min(f(i, k) + f(k+1, j)). Tuy nhiên nếu công thức kiểu như vậy thì không thể giải quyết được việc gộp 2 đoạn.
• Ý tưởng là giả sử khi xóa đoạn [i, j], ta có thể để lại 1 chữ số C đến cuối cùng. (Tại sao lại không để lại 2 chữ số?). Đặt g(i, j, c, x) = giá trị lớn nhất nếu khi xóa đoạn [i, j], ta để lại đúng x chữ số c. Chú ý là cần có chiều x, do đôi khi ta cần xóa vài chữ số c ở giữa, nhưng đến cuối vẫn để lại chữ số c để xóa cuối cùng.
• Như vậy f(i, j) = max( g(i, j, c, x) + x*x ).
• Đến đây thì còn 2 vấn đề:
  • Làm thế nào để tính g(i, j, c, x) hiệu quả?
  • c có tính chất gì?

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à :@)