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