1159.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 44 行

#include <stdio.h>
#include <memory.h>
#include <string.h>
#define min(a,b) (((a)<(b))?(a):(b))

short mem[3][5001], *ans=mem[0], *temp1=mem[1], *temp2=mem[2];
char w[5001];

int main()
{
	short i, j, l, n, *t;
	
	scanf( "%hd", &n );
	scanf( "%s", w );
	
	memset( temp1, 0, sizeof(short)*n );
	memset( temp2, 0, sizeof(short)*n );

	for( l=1; l<n; l++ )
	{
		for( i=0,j=l; i+l<n; i++,j++ )
		{
			ans[i] = ( w[i] == w[j] ) ? temp2[i+1] : 9999;

			ans[i] = min( ans[i] , temp1[i+1] + 1 );
			ans[i] = min( ans[i] , temp1[i] + 1 );
			
		}

		t = ans;
		ans = temp2;
		temp2 = temp1;
		temp1 = t;
	}

	printf( "%hd\n", temp1[0] );

	return 0;
}