QBPAL - Đếm Chuỗi đối Xứng - Tutorial SPOJ

Tutorial SPOJ Hướng dẫn và chia sẻ lời giải cho các problems trên vn.spoj.com

• « No results found »

• View more results »

Navigation
• Home
• Categories
• Search
• Wiki
• About Us
• XML Feed

Tags: bignum, dp

Problem

https://vn.spoj.com/problems/QBPAL

https://oj.vnoi.info/problem/QBPAL

Trong một buổi học viết chữ, Bờm phát hiện trong một số từ khi bỏ đi một số ký tự thì đọc ngược hay đọc xuôi đều giống nhau.

Ví dụ từ IOICAMP, khi xóa đi các chữ cái C,A,M,P, thì còn lại IOI là một từ đối xứng.

Bờm cảm thấy thú vị, và cậu tiếp tục thử xóa các ký tự khác, kết quả là có thêm nhiều từ đối xứng nữa: II, I, O, C… Nhưng nếu với một từ dài, cứ thử từng cách xóa như vậy thì thật mất thời gian. Bạn hãy viết chương trình giúp Bờm tính số cách xóa sao cho từ thu được đối xứng. Hai cách xóa chỉ khác nhau bởi thứ tự xóa các ký tự thì coi như trùng nhau.

Input

Một dòng duy nhất là từ cần tính số cách xóa, từ này chỉ chứa các chữ cái in hoa A, B, .., Z. ( Độ dài từ không quá 120 )

Output

Một số duy nhất là số cách xóa.

Example

Input IOICAMP Output 9

Tutorial

Gọi F[i][j] là số con đối xứng của đoạn i-j.

Nếu i = j thì F[i][j] = 1.

Nếu i = j-1: nếu s[i] = s[j] (ví dụ II) thì F[i][j] = 3, else F[i][j] = 2

Nếu i < j-1 thì : F[i][j] hình thành từ i,j-1 với i+1,j. Nhưng có thể ở hai lần tính này tính hai lần cho các xâu nằm trong i+1,j-1 (tức là không đả động gì đến hai phần tử biên), do đó trừ đi một lần đoạn i+1,j-1.

Tức là F[i][j] = F[i+1][j] + F[i][j-1] – F[i+1][j-1].

Sau đó, trong trường hợp s[i] = s[j] (tức là I…AIDS…I chẳng hạn) thì sẽ hình thành thêm : trước hết là xâu tạo bởi hai phần tử này (II). Thứ hai, Các xâu trong đoạn i+1,j-1 lại được tạo mới do hai phần tử này góp vào.

Do đó F[i][j] += F[i+j][j-1] + 1

Cài số lớn.

Submission

QBPAL.cpp Hide View on Github Download Copy Nếu bạn thấy bài viết này hay, hãy share bài viết này cho mọi người nhé 😉.Share this post → Tweet

Related Posts

• BONUS - VOI 2011 Phần thưởng (Categories: dp)
• ZABAVA - ZABAVA (Categories: dp, math)
• XUCXAC - Xúc xắc (Categories: dijkstra, dp, heap, data-structure)
• WEATHER - Điều kiện thời tiết (Categories: tarjan, dfs, graph, dp, math)
• VSTEPS - Steps - Bậc thang (Categories: dp)
• VOSTRIBO - Tribonacci (Categories: matrix, math, dp)
• VOSSEVEN - Bài toán số 7 (Categories: dp)
• VDANGER - Nguy hiểm rõ ràng trước mắt (Categories: dijkstra, dp, graph)

« QBMST - Cây khung nhỏ nhất ( HEAP ) QBPOINT - Bộ ba điểm thẳng hàng »