樣例輸入

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 换低档装置的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。