3177555_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
	char str[256];
	int len, i, j, k, l;
	int marka, markb, min;
	int dpa[256][256], dpb[256][256];
	int best[256];

	scanf("%s",str);
	len = strlen(str);
	memset(dpa,0,sizeof(dpa));
	memset(dpb,0,sizeof(dpb));
	for(l = 0; l < len; l++)
	{
		if(str[l]=='a')
			dpa[l][l] = 1;
		else
			dpb[l][l] = 1;
	}
	for(l = 3; l <= len; l++)
	{
		for(i = 0; i <= len-l; i++)
		{
			marka = 0;
			markb = 0;
			for(j = i+1; j < i+l-1; j++)
			{
				for(k = j+1; k <= i+l-1; k++)
				{
					if((dpa[i][j-1]==1&&dpa[k][i+l-1]==1)||(dpb[i][j-1]==1&&dpb[k][i+l-1]==1))
					{
						if(dpa[j][k-1]==1)
							marka = 1;
						if(dpb[j][k-1]==1)
							markb = 1;
					}
					if(marka==1&&markb==1)
						break;
				}
				if(marka==1&&markb==1)
					break;
			}
			dpa[i][i+l-1] = marka;
			dpb[i][i+l-1] = markb;
		}
	}
	best[0] = 1;
	best[1] = 2;
	for(i = 2; i < len; i++)
	{
		if(dpa[0][i]==1||dpb[0][i]==1)
			best[i] = 1;
		else
		{
			min = i+1;
			for(j = 0; j < i; j++)
			{
				if((dpa[j+1][i]==1||dpb[j+1][i])&&best[j]+1 < min)
				{
					min = best[j]+1;
				}
			}
			best[i] = min;
		}
	}
	printf("%d\n",best[len-1]);
	return 0;
}