02-线性结构4 Pop Sequence
02-线性结构4 Pop Sequence (25分)
- 时间限制:400ms
- 内存限制:64MB
- 代码长度限制:16kB
- 判题程序:系统默认
- 作者:陈越
- 单位:浙江大学
https://pta.patest.cn/pta/test/3512/exam/4/question/62615
Given a stack which can keep MMM numbers at most. Push NNN numbers in the order of 1, 2, 3, ..., NNN and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if MMM is 5 and NNN is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): MMM (the maximum capacity of the stack), NNN (the length of push sequence), and KKK (the number of pop sequences to be checked). Then KKK lines follow, each contains a pop sequence of NNN numbers. All the numbers in a line are separated by a space.
Output Specification:
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.
Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO
用回溯法(dfs)判断能否构造出目标序列
#include<bits/stdc++.h>
using namespace std; int gode[];
int M,N,K,num;
stack<int> Sta; bool dfs(int ipush,int ipop)//ipush,ipop为已完成的操作(push,pop)数
{
if(ipop==N)//成功构造gode
return true;
if(ipush<N&&Sta.size()<M)
{
Sta.push(num++);
if(dfs(ipush+,ipop)) return true;
num--;
Sta.pop();
}
if(ipop<ipush&&!Sta.empty()&&Sta.top()==gode[ipop])//栈顶元素即为gode的下一个数时才执行pop
{
int t=Sta.top();
Sta.pop();
if(dfs(ipush,ipop+)) return true;
Sta.push(t);
}
return false;
}
int main()
{
cin>>M>>N>>K;
for(int i=;i<K;i++)
{
num=;
for(int j=;j<N;j++)
cin>>gode[j];
puts(dfs(,)?"YES":"NO");
}
return ;
}
最新文章
- iOS 9.3真机适配-Could not find Developer Disk Image问题
- python开发目录合并小工具 PathMerge
- Single Responsibility Principle 单一职责原则
- PHP5.2至5.6的新增功能详解
- 基于Jenkins的环境搭建
- Linux系列笔记 - 用户以及用户组命令
- 忘记 oracle11g 的 sys 密码的处理
- UVA 10245 - The Closest Pair Problem
- 用bat使用date和time命令
- HttpClient 4.3.* 上传带中文文件名文件文件名乱码问题的解决
- SDP (Session Description Protocol)
- 解决SQL查询总是超时已过期
- C# 显式创建线程 or 使用线程池线程--new Thread() or ThreadPool.QueueUserWorkItem()
- Win10系统下装Ubuntu虚拟机的遇到的问题总结
- 5行代码实现微信小程序图片上传与腾讯免费5G存储空间的使用
- python基础知识14---迭代器、生成器、面向过程编程
- 轻量级web富文本框——wangEditor使用手册(4)——配置下拉菜单 demo
- POJ 1511 Invitation Cards / UVA 721 Invitation Cards / SPOJ Invitation / UVAlive Invitation Cards / SCU 1132 Invitation Cards / ZOJ 2008 Invitation Cards / HDU 1535 (图论,最短路径)
- 第十届Mockplus ▪ UXPA用户体验西南赛区决赛成功举行
- 了解ORACLE培训OCA-OCP-OCM课程表