2010年1月7日星期四.sgu170
sgu170:
简单题。
题意很简单，就是求两个只有+-组成的字符串，通过互换相邻的两个+-，是否能够由第一个串，变成第二个，给出最短的变换步数。
直觉的想法：广搜
这样显然有问题，字符串长5000，怎么搜复杂度都太高。
猜想:贪心
对于两个字符串a，b，相同的两个区间，如果a[s....t] 和
b[s...t]所含的+-数量一样多，那么由a[s...t] 到 b[s...t]
的最小距离一定是其中减号或者加号的差的绝对值的和
比如:
-+-+-
到
---++
最小步数就是0 + 1 + 2 = 3
本题就直接求两个串的符号差即可
1 http://www.cppblog.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