ZeroJudge A133: The Twin Towers

同題：UVa 10066 – The Twin Towers

很久以前在一個古老師王國有兩座形狀不同的塔聳立在兩個不同的城市裡。塔是以圓形磁磚疊起來的。每塊磁磚的高度相同且半徑均為整數。因此，儘管兩座塔形狀不同，卻包含了許多相同的磁磚。

然而在建塔的一千多年後，國王命令建築師移除某些磁磚好使兩座塔的形狀大小都相同，並且要維持可能的最大高度。磁磚的順序須與原始建築相同。國王認為這樣可以象徵兩個城市的和諧與平等。他名之為「雙子星塔」。

現在，大約兩千年後，你被賦予一個更簡單的任務：給你兩座塔的描述，你只要找出可能的最大磁磚數。

範例測資

範例輸入範例輸出
EOF 輸入，每筆測資代表一對雙子星塔。
每筆測資的第一行有兩個整數 N1 及 N2 (1 <= N1、N2 <= 100) 代表兩座塔的磁磚數。下一行含有 N1 個正整數，代表第一座塔由上而下磁磚的半徑。下一行的 N2 個整數則是第二座塔由上而下磁磚的半徑。
N1 及 N2 為 0 代表輸入結束。		對於每一對雙子星塔，輸出它的編號及每座塔所能保留的最大可能磁磚數。測資間請空一行。
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0		Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6
ZeroJudge A133 範例測資

解題思路

宣告一個二維陣列，並且跑一個 N1*N2 的 For 迴圈，如果 N1[i] == N2[j]，則要判斷使否有任一數值是第一個，也就是 0，如果 i 或 j 有一個是 0 的話，則將 二維陣列[i][j] 設為 1，否則將 二維陣列[i][j] 設為 二維陣列[i-1][j-1]。

如果兩數不相等，則也要判斷 i 或 j 是否有 0，如果都不是的話就是將 二維陣列[i][j] 設為 二維陣列[i-1][j-1]。除此之外還要判斷只有 i 或 j 其中一個等於 0 的情況，這種情況就是將數值設為另一個不是 0 的那邊 -1 位置。如果都是 0 的話就將 二維陣列[i][j] 設為 0。

最後的答案就是 二維陣列[N1-1][N2-1]。

範例程式碼－ZeroJudge A133: The Twin Towers

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M, towers = 1;
    while (cin >> N >> M && N != 0 && M != 0) {
        if (towers != 1) cout << "\n";
        int N1[200] = {}, N2[200] = {}, DP[200][200] = {};
        for (int i = 0; i < N; i++) {
            cin >> N1[i];
        }
        for (int i = 0; i < M; i++) {
            cin >> N2[i];
        }
        for (int i = 0; i<N; i++) {
            for (int j = 0; j<M; j++) {
                if (N1[i] == N2[j]) {
                    if (i-1 >= 0 && j-1 >= 0) {
                        DP[i][j] = DP[i-1][j-1] + 1;
                    }
                    else {
                        DP[i][j] = 1;
                    }
                }
                else {
                    if (i-1 >= 0 && j-1 >= 0) {
                        DP[i][j] = max(DP[i][j-1], DP[i-1][j]);
                    }
                    else if (i-1 >= 0) {
                        DP[i][j] = DP[i-1][j];
                    }
                    else if (j-1 >= 0) {
                        DP[i][j] = DP[i][j-1];
                    }
                    else {
                        DP[i][j] = 0;
                    }
                }
            }
        }
        cout << "Twin Towers #" << towers << "\n" << "Number of Tiles : " << DP[N-1][M-1] << "\n";
        towers++;
    }
}

//ZeroJudge A133
//Dr. SeanXD
標籤

相關文章

發佈留言