FZU2018级算法第三次作业 3.16 station

题目大意：

　　给出1-n共n个数的入栈顺序，可以随时出栈，求出栈的最大字典序。

输入示例	输出示例
5 1 2 3 4 5	5 4 3 2 1
5 4 2 5 3 1	5 3 2 4 1

题目分析：

　　假设目前的栈顶元素为x,若后续有大于x的数字ai出现，则ai入栈时出栈字典序一定更大。因此，对入栈进行模拟，然后将栈顶一直弹出直到栈为空或栈顶元素小于后缀最大值即可。

　　如果对于每个数后的最大值都进行一次暴力搜索，时间复杂度为O（n^2）。因此需要优化，不能暴力搜索。

　　这里引进动态规划思想。我们用dp[i]表示数组中，第i+1项到最后一项的最大值，而第i+1项开始的最大值为i+2项开始的最大值和a[i]取最大值，因此可以建立转移方程dp[i]=max(dp[i+1],a[i]);从最后一项往第一项开始扫一遍即可，O(n)预处理出后缀最大值，然后按模拟即可。

　　下面贴上AC代码。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+;

stack<int> s;

int a[maxn],dp[maxn];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n;

    cin>>n;

    for(int i=;i<n;i++) cin>>a[i];

    dp[n-]=;

    for(int i=n-;i>=;i--) dp[i]=max(dp[i+],a[i+]);

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

    {

        s.push(a[i]);

        while(!s.empty()&&s.top()>dp[i])

            cout<<s.top()<<" ",s.pop();

    }

    return ;

}

巴特西

FZU2018级算法第三次作业 3.16 station

最新文章

热门文章