问题描述：回文串就是从左看和从右看长的一样的字符串！！！例如S，AXA和MAKAM都是回文串，AYAZ很显然就不是了；现在对给定一个由大写字母组成字符串，可以删除任意位置任意个数（可以是0）个字符，使得剩下的子串是回文串，问最多有多少种这种子串？第1行，1个整数N，表示有多少组测试数据(<=15)；
接下来N行，每行一个长度不超过60的字符串；
Sample Input：3BAOBABAAAAABASampleOutput：22155
题解：
60的长度甚至可以容许优化较好的爆搜。。。正解是O(n^2)然而我写的是O(n^3)A了这题；
首先可以设状态f[i][j]表示[i,j]这段区间的所有回文子串个数，那么答案就是f[1][n]；
主要是难在状态的转移；
显然一个回文串两端加上两个相同字符仍是回文子串，那么我们从区间端点考虑转移；
枚举除i,j以外的区间内的字符k；
如果str[i]==str[k]，那么这个对区间的贡献就是f[i+1][k-1]+1；
(即i-k这一对和f[i+1][k-1]所有回文子串两端加上ik)
同样的，当str[k]==str[j]，区间的答案再加上f[k+1][j-1]+1；
当这些枚举完了之后，还有一些未加入区间答案的；
就是ij单个字母组成的串，和f[i+1][j-1]这段原有的回文子串；
特别的，当str[i]==str[j]，还有f[i+1][j-1]+1的答案需要计入；
像这样枚举每个区间处理答案就可以AC此题了；
HINT：
1.我有爆int的错觉所以开了long long ，但是写完测个极限数据并不会爆；
2.枚举区间的顺序啥的。。不必细说了吧；
3.总感觉自己讲题不会说人话了。。。虽然写题解说的也不怎么样；
说了一堆之后同学们一脸困惑的看着我这怪我咯，还有一个我刚写完状态就说这个也转移不了的。。。
教练我要讲题的技巧！
4.正解懒得写了，，意识上理解了一下。。。
str[i]==str[j]：
f[i][j]=f[i+1][j]+f[i][j-1]+1；//这里加了一个f[i+1][j-1]减了一个f[i+1][j-1]约掉了
str[i]!=str[j]：
f[i][j]=f[i+1][j]+f[i][j-1]+f[i+1][j-1]；
转移就是这坨，容斥原理理解一下就可以优化到O(n^2)了；
5.考试时候的一点小发现，读字符串可以写为scanf("%s",str+1);
这样下标就会从1开始了，之后其他字符串函数调用str+1就好；
为使用树状数组提供了方便(然而写完树状数组发现没用上)；
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 100using namespace std;typedef long long ll;ll f[N][N];char str[N];int main(){freopen("palindorme.in","r",stdin);freopen("palindorme.out","w",stdout);int c, T, n, m, i, j, k;scanf("%d", &T);for (c = 1; c <= T; c++){scanf("%s", str + 1);n = strlen(str + 1);memset(f, 0, sizeof(f));for (i = 1; i <= n; i++)f[i][i] = 1;for (j = 1; j <= n; j++){for (i = j – 1; i > 0; i–){for (k = i + 1; k < j; k++){if (str[k] == str[i])f[i][j] += 1 + f[i + 1][k – 1];if (str[k] == str[j])f[i][j] += 1 + f[k + 1][j – 1];}f[i][j] += f[i + 1][j – 1] + 2 + (str[i] == str[j] ? 1 + f[i + 1][j – 1] : 0);}}printf("%lld\n", f[1][n]);}return 0;}
有时不但是必要的，而且是很有必要的。
