pku1159.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 48 行

#include <stdio.h>


int main()
{
	char s1[5000], s2[5000];
	int l, i, j;
	int DP[2][5001];

	while (scanf("%d", &l) != -1 && l != 0)
	{
		scanf("%s", s1);

		for (i = 0; i < l; i++)
		{
			s2[i] = s1[l - i - 1];
		}
		s2[l] = 0;

		for (i = 0; i <= l; i++)
		{
			DP[0][i] = 0;
		}
		DP[1][0] = 0;

		for (i = 1; i <= l; i++)
		{
			for (j = 1; j <= l; j++)
			{
				if (s1[i - 1] == s2[j - 1])
				{
					DP[i%2][j] = DP[(i - 1) % 2][j - 1] + 1;
				}
				else if (DP[(i - 1) % 2][j] > DP[i%2][j - 1])
				{
					DP[i % 2][j] = DP[(i - 1) % 2][j];
				}
				else
				{
					DP[i % 2][j] = DP[i % 2][j - 1];
				}
			}
		}
		printf("%d\n", l - DP[l % 2][l]);
	}
	return 0;
}