码题集
题目描述
小度喜欢单调序列。一天,小度得到了一个序列,他决定把这个序列拆分成两个序列:一个是(非严格)上升序列,一个是(非严格)下降序列。小度猪脑过载了,你能帮帮他吗?
已知一个正整数序列a1,a2, …… an,你需要判断能否将a序列恰好划分成两个非空子序列(a序列中的每个元素属于且仅属于其中一个子序列),使得一个是(非严格)上升序列,另一个是(非严格)下降序列。
格式
输入格式:
输入的第一行为一个整数n,表示序列长度。
输入第二行为n个整数a[i]。
输出格式:
输出仅一行,如果存在合法的划分方案,输出”yes”(不含引号),否则输出”no”(不含引号).
备注
样例解释
其中一种分法是{1,1,4,4}和{5,1}。
数据规模及约定
n≤10^5 ,1≤ai≤10^9
样例
输入:
6
1 1 4 5 1 4
输出:
yes
算法1
(dfs)
时间复杂度
不知
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
stack <int> up;
stack <int> down;
int check(int i)
{
if (i == n + 1 && up.size() && down.size()) return 1;
if (up.size() == 0 || a[i] >= up.top())
{
up.push(a[i]);
if (check(i + 1)) return 1;
up.pop();
}
if (down.size() == 0 || a[i] <= down.top())
{
down.push(a[i]);
if (check(i + 1)) return 1;
down.pop();
}
return 0;
}
int main( )
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
if (check(1)) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
算法2
(bfs)
时间复杂度
不知
C++ 代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define cinios (ios::sync_with_stdio(false), cin.tie(0), cin.tie(0))
#define rep(i,x,n) for(int i=x;i<=n ;i++)
#define dwn(i,n,x) for(int i=n;i>=x ;i--)
#define x first
#define y second
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
typedef long long LL;
const int mod = 998244353;
int main() {
queue<PII> q;
//存的是到第 j 步时的栈顶元素(后续添加元素时作为比较的”门槛“元素)
//PII 第一个元素是上升序列的最后一个元素,第二个是下降序列的
int cnt = 1;//q.size()
int n, a[N], st[N];
cin >> n;
rep(i, 1, n) {
scanf("%d", &a[i]);
}
q.push({ 0, 1e9 + 10 });
//初始化,方便后续存 (非严格)上升序列 和 (非严格)下降序列 的第一个元素
rep(i, 1, n) {
int cnt = q.size();
// printf("%d\n",cnt);
if (cnt == 0) {
break;
}
rep(j, 1, cnt) {
PII p = q.front(); q.pop();
int x = p.x, y = p.y;
//printf("(x = %d y = %d) ",x,y);///////
//printf(" a[i] = %d \n", a[i]);/////
if (a[i] >= x) {
q.push({ a[i], y });
//如果满足条件,则将该数存入
//a[i] 为当前的上升序列的”门槛“元素,y 为下降序列的门槛元素
//因为将该数录入了上升序列,因此 x 值改变, y 值不变
}
if (a[i] <= y) {
q.push({ x, a[i] });
}
}
}
if (q.size()) {
printf("yes\n");
}
else {
printf("no\n");
}
}
/*
结构体排序方式之一:
重载小于号:bool operator< (const 结构体名称& tmp) const
{
return x > tmp.y;
}
for (int i = 1; i <= (1 << n); i++) { //1<<n就是2的n次方啦!(这样比pow函数更快哦!)
栈:先进后出
队列:先进先出
前序遍历:根左右
中 :左根右
后 :左右根
INT_MIN, INT_MAX 的头文件 --> #include <limits.h>
*/
真是奇怪为什么dfs能AC,这时间复杂度难以估计
确实,这个我也没完全搞懂