1. 给定一个字符串s， 1 <= len(s) <= 3000, 定义odd palindrome string为长度为奇数的回文串， 求s中该奇回文串的个数。
比如axbcba ， 结果为12.
实在想不出来该怎么做，想到一个笨办法，但是tle。 考察左边a对回文串的贡献， 它依次跟右边的a配对，使得这两个a之间的奇回文串翻倍，然后做记忆化搜索。
#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + ;
const int mod = 1e9 + ; ll dp[][];
string s;
ll work(int x, int y) {
if(x > y) return ;
if(x == y) return ;
ll& res = dp[x][y];
if(res != ) return res;
res++;
for (int j = y; j > x; j--) {
if(s[j] == s[x]) {
res = (res + work(x + , j - )) % mod;
}
}
res = (res + work(x + , y)) % mod;
return res;
}
void solve() {
for (int i = ; i < ; i++) {
s += (char) ('a' + i % );
}
//cin >> s;
cout << s << endl;
cout << work(, s.size() - ) << endl;
} int main() {
freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios::sync_with_stdio();
cin.tie(); cout.tie();
solve();
return ;
}
问了下，同学的方法，解法比较巧妙。对每一个字符，求左右2边的相同子序列的个数。寻找递推方程。
int dp[][];
int solve(string s) {
int n = s.size(), res = ;
memset(dp, , sizeof(dp));
for(int i = ; i <= n; i++){
for(int j = n; j > i; j--){
if(s[i-] == s[j-]){
dp[i][j] = (dp[i-][j] + dp[i][j+] + ) % MOD;
}
else{
dp[i][j] = ((dp[i-][j] + dp[i][j+])%MOD +(- dp[i-][j+]) )%MOD;
}
}
}
for(int i = ; i <= n; i++){
res = ((res + dp[i-][i+])%MOD + ) % MOD;
}
return res;
}
看了这个解法，我就感觉有点在哪里见过的赶脚， 然后想到以前做过的一道题， 数字符串s里面回文子序列的个数。
就是这个题目：https://hihocoder.com/problemset/problem/1149 当时什么都不懂， 现在大概有点想法了。
这个题目的代码如下：
#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + ;
const int mod = ;
ll dp[][];
char s[];
void solve() {
scanf("%s", s);
memset(dp, , sizeof dp);
int n = strlen(s);
for (int j = ; j <= n; j++) {
for (int i = ; i <= n; i++) {
int r = i + j - ;
if(j == ) {
dp[i][r] = ;
} else {
if(s[i - ] == s[r - ]) {
dp[i][r] = (dp[i][r - ] + dp[i + ][r] + ) % mod;
} else {
dp[i][r] = ((dp[i][r - ] + dp[i + ][r] - dp[i + ][r - ]) % mod + mod) % mod;
}
}
}
}
printf("%lld\n", dp[][n]);
} int main() {
freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
//ios::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
int _;
scanf("%d", &_);
for (int i = ; i <= _; i++) {
printf("Case #%d: ", i);
solve();
}
return ;
}
然后，我就想着，这道题目能不能这样做呢， 其实也是可以的。
定义dp[i][j],为区间[i. j]奇回文的个数， 显然长度为1的时候为1， 长度为2的时候为2， 然后转移方程就跟上面的hihocode回文子序列的个数差不多了。
#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + ;
const int mod = 1e9 + ;
string s;
ll dp[][];
void solve() {
for (int i = ; i < ; i++) {
s += (char) ('a' + i % );
}
//cin >> s;
cout << s << endl;
int n = s.size();
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
int l = j, r = j + i - ;
if(r > n) continue;
if(i == ) {
dp[l][r] = ;
} else if(i == ){
dp[l][r] = ;
} else {
if(s[l - ] == s[r - ]) {
dp[l][r] = (dp[l + ][r] + dp[l][r - ]) % mod;
} else {
dp[l][r] = (dp[l + ][r] + dp[l][r - ] - dp[l + ][r - ] + mod) % mod;
}
}
//cout << l << " " << r << " " << dp[l][r] << endl;
}
}
cout << dp[][n] << endl;
} int main() {
freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios::sync_with_stdio();
cin.tie(); cout.tie();
solve();
return ;
}
以前不是很了解这种dp的套路，现在大概是有点想法了。