给定一字符串，问最少插入多少字符能使该字符串变成回文串。只要求出该字符串与其逆串的公共子序列，然后然后用n减去就得结果。这里卡内存，可以将f[5007][5007]定义成short int 型，计算后能险过，所以这里最好采用滚动数组。
View Code #include#include #include #define maxn 5005using namespace std;char s[maxn];int f[2][maxn];int main(){ //freopen("in.txt","r",stdin); int n,i,j; scanf("%d",&n); scanf("%s",s + 1); f[0][0] = 0; for (i = 1; i <= n; ++i) { f[0][i&1] = 0; f[i%1][0] = 0; } for (i = 1; i <= n; ++i) { for (j = 1; j <= n; ++j) { if (s[i] == s[n - j + 1]) f[i&1][j] = f[(i - 1)&1][j - 1] + 1; else { f[i&1][j] = max(f[(i - 1)&1][j],f[i&1][j - 1]); } } } printf("%d\n",n - f[n&1][n]); return 0;}