UVa1588 | 算法竞赛入门经典(第二版) 习题3-11 换低档装置

样例输入

2112112112
2212112
12121212
21212121
2211221122
21212

样例输出

10
8
15

解题思路：

最开始设想了四种情况， A固定， B左移或右移，或B掉头，左移或右移， 但经验告诉我不可能这么麻烦，
经过搜网后， 发现陷入了一个误区：在日常生活中是可以掉头的，但是在题给中，块由数字组成，所以掉头数字也会
变动，就不是同一个木块了。

因此就只剩下了两种情况， A固定，B左移或右移， 可以利用其对称性简化为一种， 也就是写一个函数，根据
传入参数的不同， 执行不同的情况：A固定，B右移 等价于 A左移，B固定。 缩短代码长度。

代码

#include <iostream> #include <cstdio> #include <string.h> #include <string> #include <algorithm>using namespace std ;//判断木块S2位移为k时，是否符合要求 bool test(int k , char s1[] , char s2[] ) {for ( int i = 0 ; s1[k+i] && s2[i] ; i++ ) if(s1[k+i] + s2[i] - 2*'0' > 3) return false ; return true ; }//返回符合要求的情况 int fun(char s1[] , char s2[]) {int k = 0 ; while(!test(k,s1,s2)) //当不符合条件时，移位。 k++ ; //为什么返回最大？ //若还是S1更长，则返回S1 ， 若S2位移了若干位后更长，则返回S2 return max(strlen(s1) , strlen(s2)+k) ; } int main() {char bottom[105] ; //上面的木块char top[105] ; //下面的木块while(scanf("%s%s",bottom,top) != EOF) //下条语句判断左移最优解还是右移最优解。 cout << min(fun(bottom,top),fun(top,bottom)) << endl ; //调用algorithm中函数 return 0 ; }

收获：普适性的情况可以写函数解决，要养成好习惯。

总结

以上是生活随笔为你收集整理的UVa1588 | 算法竞赛入门经典(第二版) 习题3-11 换低档装置的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。