#include <stdio.h>
#include <memory.h>

#define MAXN 5001
#define min(x,y) ((x) < (y) ? (x) : (y))
int s[2][MAXN];

int main() {
	char a[MAXN];
	int n;
	
	scanf("%d\n%s", &n, a);
	
	for (int k=2; k<=n; k++) {
		int k1 = k&1;
		int k2 = (k+1)&1;
		for (int i=0; i<=n-k; i++) {
			int j=i+k-1;
			if (a[i] == a[j])
				s[k1][i] = s[k1][i+1];
			else
				s[k1][i] = min(s[k2][i], s[k2][i+1]) + 1;
		}
	}
	printf("%d\n", s[n&1][0]);
}

• Re:高手们300+,400+MS是怎么弄的啊？我觉得我这DP代码已经很精简了，还要500+…… (14) Fatedayt 2011-09-02 12:35:36
• Re:高手们300+,400+MS是怎么弄的啊？我觉得我这DP代码已经很精简了，还要500+…… (14) Fatedayt 2011-09-02 12:35:42