学步园

UVA_11151

    状态转移方程为：①b[i]==b[j]，f[i][j]=f[i+1][j-1]+(i==j?1:2)；②b[i]!=b[j]，f[i][j]=max{f[i+1][j],f[i][j-1]}。

#include<stdio.h>
#include<string.h>
#define MAXD 1010
int N, f[MAXD][MAXD];
char b[MAXD];
void solve()
{
int i, j, k;
    gets(b);
    N = strlen(b);
    memset(f, 0, sizeof(f));
for(k = 0; k < N; k ++)
for(i = 0; i + k < N; i ++)
        {
if(b[i] == b[i + k])
                f[i][i + k] = f[i + 1][i + k - 1] + (i == i + k ? 1 : 2);
else
                f[i][i + k] = f[i + 1][i + k] > f[i][i + k - 1] ? f[i + 1][i + k] : f[i][i + k - 1];
        }
    printf("%d\n", f[0][N - 1]);
}
int main()
{
int t;
    gets(b);
    sscanf(b, "%d", &t);
while(t --)
    {
        solve();
    }
return 0;
}