http://acm.pku.edu.cn/JudgeOnline/problem?id=3401
String reduction
| Time Limit: 1000MS |
Memory Limit: 65536K |
|
| Total Submissions: 799 |
Accepted: 219 |
Description
There
is a string of characters 'a' and 'b' with the length of no more
than 255 characters. You can perform the substring reduction on the initial
string in the following way: a substring "a*a" or "b*b"
(where *(asterisk) denotes any character) can be reduces to a substring
"*".
The
task is to achieve a string of minimal possible length after several substring
reductions.
Input
The
input contains the initial string.
Output
The
output contains a single line with the minimal possible length.
Sample Input
aab
Sample Output
3
Source
Europe 2001, Western Subregion
a*a,b*b的字符变为a或者b，要求
F[i+1][j-1] = = true
true || F[i][j-2] ==true)
表示i，j之间的字串能够变为的最小长度，可以看出这个也是一个标准的动态规划
2,Len[i+1][j]+1,Len[i][j-1]+1)
后来突然发现这个题目有一个非常桥面简单的方法，由于a*a, b*b之类的字符可以匹配任意字符，那么我们只要从前
向后扫描，如果有相隔的两个字符相同，由于这三个字符能够匹配a,b任意字符，那么我们就可以让这种匹配一直进行
下去，从而将字符串不断的reduction ，只要注意字符串长度的奇偶性就可以了，如此我们可以得到一个很简单的方法
代码如下：