2010年1月7日星期四.sgu170
sgu170:
簡單題。
題意很簡單，就是求兩個只有+-組成的字符串，通過互換相鄰的兩個+-，是否能夠由第一個串，變成第二個，給出最短的變換步數(shù)。
直覺的想法：廣搜
這樣顯然有問題，字符串長5000，怎么搜復雜度都太高。
猜想:貪心
對于兩個字符串a，b，相同的兩個區(qū)間，如果a[s....t] 和
b[s...t]所含的+-數(shù)量一樣多，那么由a[s...t] 到 b[s...t]
的最小距離一定是其中減號或者加號的差的絕對值的和
比如:
-+-+-
到
---++
最小步數(shù)就是0 + 1 + 2 = 3
本題就直接求兩個串的符號差即可
1 http://www.shnenglu.com/schindlerlee
2 bool judge()
3 {
4 len1 = strlen(stra);
5 len2 = strlen(strb);
6 if(len1 != len2) return false;
7 int i,res = 0;
8 for(i = 0;i < len1;i++) {
9 if(stra[i] == '-') { out1[top1++] = i; }
10 if(strb[i] == '-') { out2[top2++] = i; }
11 }
12 if(top1 != top2) return false;
13 for(i = 0;i < top1;i++) {
14 res += abs(out1[i] - out2[i]);
15 }
16 printf("%d\n",res);
17 return true;
18 }
19
20