UVAOJ10152 | 哈喽哈咯

Written by razrlele 22:56 December 20, 2014

题意:

首先给出一堆栈乌龟, 然后每个乌龟都可以爬到顶端去, 然后求最少爬的次数以及先后顺序以达到目的堆栈乌龟的顺序.

思路:

既然要求最小次数, 那么乌龟一定分两种, 一种是一次都不用爬只用保持原位置不懂或者随着其它乌龟往上爬而自然往下移的, 另外就是需要爬的.

判断一个乌龟是否需要爬的依据就是它在初始堆栈里面的位置上面的乌龟在目的堆栈中在它下面, 然后需要注意的是不用动的乌龟在目的堆栈中一定是由下往上连续的, 所以可以在目的堆栈中由下往上一个一个判断乌龟是否需要爬, 按照目的堆栈的顺序由下往上一个一个输出需要爬的乌龟即为最佳方案.

注意题目要求在只有一只乌龟的时候最佳方案是这只乌龟爬而不是零, 然后0乌龟的情况也要输出一个空格, 当时程序卡在送了好多RE ԅ(¯﹃¯ԅ)

* File Name: uvaoj10152.cpp

* Author: razrLeLe

* Mail: razrlele@outlook.com

* Homepage: https://yueyu.io

* Created Time: 2014年12月18日星期四 19时53分59秒

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int maxn = 510;

string turtlestack[maxn];

string finalans[maxn];

map<string, int> turtleid;

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

int K, n;

cin >> K;

int count = 1;

while(K--)

{

cin >> n;

if(n <= 0)

{

//cout << endl << count++ << endl << n << endl;

cout << endl;

continue;

}

getchar();

turtleid.clear();

for(int i = 0; i < n; i++)

{

getline(cin, turtlestack[i]);

}

for(int i = 0; i < n; i++)

{

getline(cin, finalans[i]);

turtleid.insert(pair<string, bool>(finalans[i], false));

}

int flaga = n-1, flagb = n-1;

while(!turtleid[finalans[flaga]] )

{

while(turtlestack[flagb] != finalans[flaga])

{

turtleid[turtlestack[flagb]] = true;

flagb--;

}

flaga--;

flagb--;

if(flaga < 0) break;

}

/*cout << endl << count++ << endl;

cout << n << endl;

for(int i = 0; i < n; i++)

cout << turtlestack[i] << endl;

cout << endl;*/

if(flaga >= 0)

{

for(int i = flaga; i >= 0; i--)

cout << finalans[i] << endl;

}

cout << endl;

}

return 0;

}