Zipper

Poj

輸入

輸入測試次數n;
每一次測試,分別輸入string a,b和all;

輸出

如果,a,b串,在 all中可以按順序找到,就輸出"yes"
否則就輸出"no"

例如

cat tree tcraete 這個是要輸出 yes的 111 000 101001 這個也是要輸出yes的 111 000 111100 這個是要輸出no的 #include <iostream> #include <cstring> #include <algorithm> using namespace std; #include <string>string a, b, all; bool Arr[1000][1000]; //Arr[i][j]表示 以 a[i]和b[j]結束的串在不在其中 在 = true,或者 不在 = false ;int find(char c, int no = -1) //no表示不是坐標no {for (int i = 0; i < all.length(); ++i){if (all[i] == c && i != no)return i;}return -1; } void oper() {int pp1 = find(a[0]);int pp2 = find(b[0], pp1); //得到在pp2 != pp1的前提下找到了b[0]的開頭,還是從前面找if (pp2 == -1){ //通過這種方式的尋找，確保了，最后一個元素在兩者中都存在cout << "no" << endl;return;} //這是一種可能，在這種可能之下Arr[0][0] = true;if (pp1 > pp2){for (int i = pp2 + 1; i < pp1; ++i){if (b[i] != all[i]){cout << "no" << endl;return;}Arr[0][i] = true;}}else{for (int i = pp1 + 1; i < pp2; ++i){if (a[i] != all[i]){cout << "no" << endl;return;}Arr[i][0] = true;}} //要明白一點，兩個開頭的位置之間的字符必定是屬于前面那個字符所對應的字符串的//至此，就開始遍歷所有的起始位置 ,兩個位置都劃歸到了同一位置//進行斜著的填表過程，每一斜行，都有，橫縱坐標相加都是相等的，就是說，考慮的都是對于all來說，都是前面的//cat tree tcraeteint p = max(pp1, pp2) + 1; //用 p來表示需要處理的all 的第p個元素(從0開始計數)，其實很明顯可以看到//目前，指定到了準確的位置while (p < all.length()){ //p表示第p個元素，就是表示第p斜行for (int i = 0; i <= p; ++i){ //對于這個第p個元素，只有三種可能，第一，這個屬于a[i]，第二，這個屬于b[j],第三個，都不屬于，則返回;bool aB = false, bB = false;if (i >= 1){if (a[i] == all[p])aB = Arr[i - 1][p - i - 1];}if (p - i - 1 >= 1){if (b[p - i - 1] == all[p])bB = Arr[i][p - i - 2];}Arr[i][p - i - 1] = aB || bB;}++p;}if (Arr[a.length() - 1][b.length() - 1])cout << "yes" << endl;elsecout << "no" << endl;return; }int main() {int n, caseNo = 0;cin >> n;while (n--){cin >> a >> b >> all;cout << "Data set " << ++caseNo << ": ";if (a.length() + b.length() != all.length()){cout << "no" << endl;continue;}memset(Arr, false, sizeof(Arr));oper();} }

總結

以上是生活随笔為你收集整理的[POJ]Zipper[动态规划]的全部內容，希望文章能夠幫你解決所遇到的問題。

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