HDU3427 - Clickomania - 區間dp+dfs+字元串處理

1.題目描述：

Clickomania

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 628    Accepted Submission(s): 318

Problem Description Clickomania is a puzzle in which one starts with a rectangular grid of cells of different colours. In each step, a player selects ("clicks") a cell. All connected cells of the same colour as the selected cell (including itself) are removed if the selected cell is connected to at least one other cell of the same colour. The resulting "hole" is filled in by adjacent cells based on some rule, and the object of the game is to remove all cells in the grid. In this problem, we are interested in the one-dimensional version of the problem. The starting point of the puzzle is a string of colours (each represented by an uppercase letter).

At any point, one may select (click) a letter provided that the same letter occurs before or after the one selected. The substring of the same letter containing the selected letter is removed, and the string is shortened to remove the hole created. To solve the puzzle, the player has to remove all letters and obtain the empty string. If the player obtains a non-empty string in which no letter can be selected, then the player loses. For example, if one starts with the string "ABBAABBAAB", selecting the first "B" gives "AAABBAAB". Next, selecting the last "A" gives "AAABBB". Selecting an "A" followed by a "B" gives the empty string. On the other hand, if one selects the third "B" first, the string "ABBAAAAB" is obtained. One may verify that regardless of the next selections, we obtain either the string "A" or the string "B" in which no letter can be selected. Thus, one must be careful in the sequence of selections chosen in order to solve a puzzle. Furthermore,

there are some puzzles that cannot be solved regardless of the choice of selections. For example, "ABBAAAAB" is not a solvable puzzle. Some facts are known about solvable puzzles: The empty string is solvable. If x and y are solvable puzzles, so are xy, AxA, and AxAyA for any uppercase letter

A. All other puzzles not covered by the rules above are unsolvable.

Given a puzzle, your task is to determine whether it can be solved or not.  

Input Each case of input is specified by a single line. Each line contains a string of uppercase letters. Each string has at least one but no more than 150 characters. The input is terminated by the end of file.  

Output For each input case, print solvable on a single line if there is a sequence of selections that solves the puzzle. Otherwise, print unsolvable on a line.  

Sample Input

ABBAABBAAB
ABBAAAAB
        

Sample Output

solvable
unsolvable
        

Source Rocky Mountain Regional Contest 2009  

Recommend zhouzeyong   |   We have carefully selected several similar problems for you:   3424  3425  3432  3428  3429   

2.題意概述：

Clickomania(彩球消除)是一款遊戲，有幾種顔色不同的方塊排成一列。每次可以将一段連續的顔色相同的方塊消除掉，消除後原本這段方塊兩端的方塊連接配接在一起，比如：ABBBA，将中間的BBB消除後，就變成了AA。現在給你一段字元串，不同的字元代表不同的顔色，問能不能将整個字元串消除完。

3.解題思路：

将字元串縮減成兩個數組，一個存出現過的字元，另一個存這個字元出現的次數。例ABBBAACC壓縮成ABAC 和 1322。從前往後掃描，每一個目前字元要麼自成一串，構成合法序列，然後判斷剩餘字元串是否合法，要麼和後面某一個相同字元合并，前提是他們中間的得是合法序列，按照這樣分類方法直接dfs() + 标記。做這種類似的題，關鍵在于找到構成這些字元串的規則或叫詞法，然後分類搜尋+标記。

4.AC代碼：

// 3427.cpp : 定義控制台應用程式的入口點。
//

#include <stdio.h>
#include <string.h>
#define N 155 
using namespace std;
char str[N], cha[N];
int dp[N][N], num[N];

int dfs(int l, int r)
{
	int i, t;
	if (l == r) 
	{   /*如果就剩一種字元，直接判斷是相連的個數是否大于1*/
		if (num[l] > 1)
			return 1;
		else
			return 0;
	}
	if (dp[l][r] >= 0)
		return dp[l][r];
	/*目前字元和後面的任一個相同字元合并，前提是夾在他們中間的字元串是合法的*/
	char ch = cha[l];
	for (i = l + 1; i <= r; i++) 
	{
		if (cha[i] == ch)
		{
			if (dp[l + 1][i - 1] = dfs(l + 1, i - 1)) 
			{
				t = dp[i][r];
				dp[i][r] = -1;
				num[i] += num[l];
				dp[i][r] = dfs(i, r);
				num[i] -= num[l];
				if (dp[i][r] == 1)
				{
					dp[i][r] = t;
					return 1;
				}
				dp[i][r] = t;
			}
		}
	}
	/*目前字元是合法的，直接判斷後一部分是否合法，即如果x，y都合法，則xy也合法*/
	if (num[l] > 1 && (dp[l + 1][r] = dfs(l + 1, r)))
		return 1;
	return 0;
}
int main()
{
	while (scanf("%s", str) != EOF) 
	{
		int len = strlen(str);
		if (len == 0) 
		{
			puts("solvable");
			continue;
		}

		/*
		将字元串縮減成兩個數組，一個存出現過的字元，另一個存這個字元出現的次數
		例ABBBAACC        縮成ABAC 和 1322
		*/
		int time = 1, step = 0;
		for (int i = 1; i <= len; i++) 
		{
			if (str[i] != str[i - 1]) 
			{
				cha[step] = str[i - 1];
				num[step] = time;
				time = 1;
				step++;
			}
			else
				time++;
		}
		memset(dp, -1, sizeof(dp));
		if (dfs(0, step - 1))
			puts("solvable");
		else
			puts("unsolvable");
	}
	return 0;
}