Nguồn đề bài: http://vn.spoj.com/problems/COUNTPL/
1. Đề bài Đếm số Palindrome
Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome. Ví dụ: Xâu ‘bobseesanna’ có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:
‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’
‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’
‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’
Chúng ta quan tâm đến việc tính hàm countpal(s) được định nghĩa là số cách sử dụng các palindrome mà có thể tạo thành xâu s nói trên.
Yêu cầu
Hãy tính giá trị hàm countpal(s) của một xâu s cho trước. Vì kết quả có thể rất lớn nên chúng ta chỉ quan tâm tới phần dư của nó khi chia cho 10^9 +7
Input
– Dòng đầu tiên ghi một số n – độ dài của xâu (0<n<=1000)
– Dòng thứ hai ghi n kí tư mô tả xâu
Output
Gồm một dòng duy nhất ghi kết quả tìm được.
2. Gợi ý Đếm số Palindrome
Lập công thức:
-Gọi f[i] là số cách phân tích xâu từ s1 đến si
Ta có: f[i]= ∑ f[j] với 1<=j<=i
sj, sj+1,…, si là một palindrome.
3. Code Đếm số Palindrome
Ver 1
#include <bits/stdc++.h>
#define t 1000000007
using namespace std;
int n;
char a[1001];
long long f[1001];
bool ok(int i, int j)
{
while (i <= j)
{
if (a[i] != a[j]) return false;
i++;
j--;
}
return true;
}
int main()
{
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
{
scanf("%c", &a[i]);
f[i] = 0;
}
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= i; j++)
if (ok(j, i)) f[i] = ((long long)f[i] + f[j - 1]) % t;
}
cout << f[n];
}
Ver 2
Ta nhận thấy nếu kiểm tra xâu sj, sj+1,…, si là một palindrome hay không, ta làm như ver 1 thì sẽ tốn rất nhiều thời gian.
do đó, ta tìm cách xử lí nó.
Đặt c[i][j]=1 hoặc 0 tùy thuộc xâu sj, sj+1,…, si là một palindrome hay không.
c[i][j]=0 nếu s[i]!=s[j];
c[i][j]= c[i+1][j-1] nếu s[i]=s[j];
Ta viết một hàm xác định xâu palin trước rồi mới tính để giải yêu cầu của bài.
