FOJ Problem 2260 Card Game

Problem 2260 Card Game

Accept: 37 Submit: 117
Time Limit: 3000 mSec Memory Limit : 32768 KB

Problem Description

有如下取牌游戏：

1. 桌面上有n张卡牌从左到右排成一行，每张卡牌上有一个数字；

2. 游戏按轮次进行，每一轮中取掉所有比左边数值小的卡牌；

3. 当无牌可取的时候则游戏结束。

比如初始卡牌为{5, 6, 3, 7, 4, 1, 2}，共需2轮取牌。取牌过程如下（小括号为每轮取掉的牌）：

{5, 6, 3, 7, 4, 1, 2}

==> {5, 6, (3), 7, (4), (1), 2}

==> {5, 6, 7, 2}

==> {5, 6, 7, (2)}

==> {5, 6, 7}

现按顺序给定初始的卡牌数字，请求出游戏结束时取牌的总轮次，并输出结束时桌上剩余的卡牌序列。

Input

包含多组测试数据。

输入包含两行。

第一行包含一个整数n表示卡牌的数量。

第二行包含n个空格隔开的整数，表示排成一行的卡牌上对应的数字(取值范围[1,1000000000])。

n≤1000000

Output

输出包含两行。

第一行包含一个整数表示游戏的取牌总轮次。

第二行包含游戏结束时桌上剩余的卡牌序列，用空格隔开。

Sample Input

5 6 3 7 4 1 2

Sample Output

5 6 7

思路：可以用栈来模拟，轮数则可用dp求得。按顺序每次取出当前数字，放往栈中，放进去之前先要与堆顶元素进行比较，若当前元素要小，则直接放入堆中即可；若当前元素大于等于栈顶元素，此时要分两种情况考虑：
1:栈中只剩栈顶元素的情况，此时栈顶元素的下面已经没有元素了，因此已经无法被消除，则一定会出现在最终的卡牌序列中，将之抛出栈中并记录，再将当前元素放入堆中；

2：栈中还有多个元素，此时只要将栈顶元素抛出即可，这一操作意味着如果当前元素被消除，栈顶元素一定在当前元素被消除轮数的前一轮被消除，即可dp求解当前元素被消除的轮数即dp[i]=max(dp[i],dp[k]+1)

上述操作合理性：模拟过程可知如果堆中存在多个元素，那么越是上面的元素数值就越小，也就是说除了栈底元素，其余的最终都将会被消除，因为在它们的左边存在比它们大的数，只是各自会在第几轮消除需要dp递归式的求解。

最后n个元素都被操作一遍之后，对栈进行清理清空操作，操作过程与上述类似。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
#define INF 0x3f3f3f3f
const int N_MAX = 1000000+2;
int a[N_MAX],n;
stack<int>s;
int dp[N_MAX];
vector<int>res;
int main() {
    while (scanf("%d",&n)!=EOF) {
        memset(dp, 0, sizeof(dp));
        res.clear();
        int term = 0;
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        for (int i = 0; i < n;i++) {
            while (!s.empty() && a[i] >= a[s.top()]) {
                if (s.size() == 1) {
                    res.push_back(a[s.top()]);
                    s.pop();
                }
                else {
                    dp[i] = max(dp[i],dp[s.top()]+1);
                    term = max(term,dp[i]);
                    s.pop();
                }
           }
            s.push(i);
        }
    
        while (!s.empty()) {
            if (s.size() == 1) {
                res.push_back(a[s.top()]);
                    s.pop();
            }
            else {
                term = max(term, dp[s.top()] + 1);
                s.pop();
            }
        }
        printf("%d
",term);
        for (vector<int>::iterator it = res.begin(); it != res.end();it++) {
            if (it + 1 != res.end())cout << *it << " ";
            else cout << *it << endl;
        }
    }
    
    return 0;
}