传送门
题意
给定一个长度为n的字符串s， 每次可以消除i，j之间的字符当第i个字符与第j个不相同时
求最小消除整个字符串的最小次数。
题解
dp解法（考场
dp还是很简单的。
考虑朴素的dp， 设(f_{i}) 表示消除前i个字符的最小花费。
容易想到
[fi = min_{1leq j < i} {f_{j-1} + 1} \,\,: (S_i
eq S_j)
]
如果我们用一个变量维护到i为止的最小的(f_{j-1})就可以(O(1))转移，但不能满足i， j的字符不同。
换一个思路， 我们用一个大小为26的数组维护，(d_i)表示最小的(f_{j-1})使得Sj 为 i
简单的说， 就是维护以某一字符结尾的最小花费
转移的时候只要这个字符不等于(Si)即可
不懂可以看看代码？
总复杂度(O(26n))
没完呢， 下面还有另一种做法
const int N = 100005;
const int inf = 0x3f3f3f3f;
int n;
int s[27];
int a[N];
int main(){
n = read();
for(int i=1; i<=n; i++){
a[i] = readc();
}
a[n+1] = 26;
for(int i=0; i<=26; i++){
s[i] = inf;
}s[a[1]] = 0;
for(int i=1; i<=n; i++){
int res = inf;
for(int j=0; j<26; j++){
if(a[i] == j) continue;
res = min(res, s[j]);
}
s[a[i+1]] = min(s[a[i+1]], res+1);
}
printf("%d
", s[26]>=inf?-1:s[26]);
return 0;
}
贪心解法（题解做法
我只能说真的妙， 这才能叫AGC把！！
先说结论： 花费只可能是1，2， 否则不可能消除。（这里给出我的证明
先说1吧， 假如字符串的首尾不相同， 显然可以一次消掉。
然后再看2， 假如首尾相同且都是a，显然不能一次消掉。我们考虑如果字符串中存在两个相邻的字符，这两个字符都不等于a，那么这个字符串可以两次消掉。
否则的话字符串中只存在一个连续的不是a，例如aba， 那么无论我们如何消除，最后都会剩下一个首尾都是a的字符串，无论如何都不能消除。