#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MAX_SIZE = 1e5+10; char text[MAX_SIZE]; /** Title: 白濑肆×字符串+DP——果然是字符串处理什么的好讨厌啊尤其是换行符的处理看来不用CIN不行了呢虽然效率低人家好伤心的还有就是DP的转移真心不会啊水到家了怎么办! Problem:CodeForces 155C Hometask Little Exp.: cin输入单个字符(char)的时候自动无视掉换行符,而scanf和getchar都不行。 pre-Knowledge: None.Only ur intellgence. Knowledge Point: DP Thx to: severin&&gzm提供的AC代码...刚开始打成serverin...弄错别人的id是很失礼的啊。。金魂(啊哈哈君你好么喂 Reference: ↑,但是其本人未公开发布,所以恕不提供啦:) Thought: 看来我果然想复杂了。 【之前的错误思路】: 根据上一次转移遗留下来的字母进行转移,看看是删除左边还是删除右边,数出合法状态数。 很明显,这D个屁P,这明显就是暴搜思路。 更不用说暴搜还没过。 【正确思路】: 每次读入一对儿禁止出现的字符S[0],S[1],注意题意中说每个字母最多在一个pair中出现。 对于读入的字符串text[i],划掉text[n..k]即可。text[n..k]有如下规定: text[n..k]的性质是对于i : n <= i <= k 有 text[i] == S[0]或text[i] == S[1]; 也就是说text[n]到text[k](包括n和k)全是不可以出现的字符。 统计一下如果是去掉s[0]【或者】去掉s[1]使得text[n..k]变成合法的,需要划掉多少次。 sum加上小的那个次数即可。 比如 aaaaabcddddd 2 ad bc 那么,在text[0..4]的时候我们需要划掉a 5次,划掉d 0 次,此时sum = sum + 0 = 0;( sum初始化为0) text[5..6]的时候需要划掉b 1次。 c 1次,此时sum = sum + 1 = 1 text[7..末尾]的时候需要划掉d 5次,a 0次,此时sum = sum + 0 = 1; 结果就是1咯 【为什么?】(高能警告:本人数学白痴,自诩这种证明方式是正确的,跪求板砖或指出证明出错的地方) 对于原始串text,以最小次数去掉其中第一对禁止字符s[]之后,剩下的串是合法的。得到串text' 对于串text',重复以最小次数去掉其中第i对禁止字符s[],得到的新串仍然是合法的 只不过我们没有改变text的内容(亦即没有真的去掉其中的字母),而是记录下了最小次数累加而已。 不用改变text内容的原因是,题意中说每个字母在禁止出现的字母对中最多出现一次。 所以禁止字母对s[],s'[]中的内容不可能相同,彼此独立。 以上,反守为攻の白濑肆 */ int main() { char a = 0; char b = 0; int K; int ans = 0; gets(text); int lent = strlen(text); scanf("%d\n",&K); for(int k = 0 ; k < K ; k++) { cin >> a; cin >> b; for(int i = 0 ; i < lent ; i++) { int left = 0 ,right = 0; while( text[i] == a || text[i] == b ) { if( text[i] == a ) left++; if( text[i] == b ) right++; i++; } ans += min(left,right); } } printf("%d\n",ans); return 0; }