3177670_ac_2933ms_2804k.java

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

import java.util.*;
import java.io.*;

public class Main
{

	public static void main(String [] args)	throws Exception
	{
		BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
		int n;
		String str;
		int len, i, j, k, l;
		int marka, markb, min;
		int [][] dpa = new int [256][256];
		int [][] dpb = new int [256][256];
		int [] best = new int [256];

		str = cin.readLine();
		len = str.length();
		for(l = 0; l < len; l++)
		{
			if(str.charAt(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++)
				{
					if(dpa[i][j-1]==0&&dpb[i][j-1]==0)
						continue;
					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]==1)&&best[j]+1 < min)
					{
						min = best[j]+1;
					}
				}
				best[i] = min;
			}
		}
		System.out.printf("%d\n",best[len-1]);
	}

}