学步园

使用滚动数组

题目：

http://acm.pku.edu.cn/JudgeOnline/problem?id=1159

#include <stdio.h><br /> #include <string.h></p> <p>#define max 5002<br /> #define MAX(x,y) (x > y ? x : y)</p> <p>//滚动数组<br /> short g[2][max];<br /> char sa[max];<br /> char sb[max];<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> int i,j,n;<br /> while(scanf("%d%s",&n,sa + 1) != EOF){<br /> memset(g,0,sizeof(g));<br /> for(i=1;i<=n;i++)<br /> sb[i]=sa[n+1-i];<br /> sb[i]='/0';<br /> for(i = 1;i <= n;i++)<br /> for(j = 1;j <= n;j++)<br /> if(sa[i] == sb[j])<br /> g[i % 2][j] = g[(i - 1) % 2][j] + 1;<br /> else<br /> g[i % 2][j] = MAX(g[(i - 1) % 2][j],g[i % 2][j - 1]);<br /> printf("%d/n",n - g[n % 2][n]);<br /> }<br /> return 0;<br /> }</p> <p>