1618 - Weak Key【贪心】【搜索】

本文主要是介绍1618 - Weak Key【贪心】【搜索】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

传送门

给出n个case
每个case中有m个数字，对于每一组case，问是否存在4个整数
Np Nq Nr Ns (1 <= p < q < r < s <= k)，使得
Nq > Ns > Np > Nr
或者
Nq < Ns < Np < Nr。

样例

input

3
6
10 30 60 40 20 50
8
30 40 10 20 80 50 60 70
4
1 2 20 9

output

YES
NO
NO

解释

第一组样例中符合题目要求的子序列是 30 60 20 50
第二组样例中不满足条件
第三组样例中不满足条件

思路

如果使用DFS那么5000的深度，有可能会爆栈
使用数组L和R来预处理。
只考虑一种情况
Np Nq Nr Ns (1 <= p < q < r < s <= k)
Nr < Np < Ns < Nq

• L[i][j]，表示下标小于j并且值比Num[i]大的数中最小值的位置
  
  • 比如L[r][q]表示下标小于q并且值比Num[r]大的数中最小值的位置，这个值就是p
• R[i][j]，表示下标大于j并且值比Num[i]小的数中最大值的位置
  
  • 比如R[q][r]表示下标大于r并且值比Num[q]小的数中最大值的位置，这个值就是s

p在空间上肯定是小于s的，因为p是由小于q得来的。
s在空间上肯定是大于p的，因为s是由大于r得来的。

代码

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include <math.h>
using namespace std;const int maxn = 5000 + 5;int num[maxn];int L[maxn][maxn];
int R[maxn][maxn];
int m;bool solve(){for(int i=1;i<=m;i++){L[i][0] = 0;for(int j=1;j<i;j++){if (num[i] >= num[j]) L[i][j] = L[i][j - 1];else if(!L[i][j-1] || num[j] < num[L[i][j-1]]) L[i][j] = j;else L[i][j] = L[i][j-1];}}for(int i=1;i<=m;i++){R[i][m+1] = 0;for(int j=m;j>i;j--){if(num[i] <= num[j]) R[i][j] = R[i][j+1];else if(!R[i][j+1] || num[j] > num[ R[i][j+1] ]) R[i][j] = j;else R[i][j] = R[i][j+1];}}for(int i=0;i<=m;i++){for(int j=i+1;j<=m;j++){if( !L[j][i-1]  || !R[i][j+1] || num[i]<=num[j]) continue;int p = L[j][i-1];int s = R[i][j+1];if (num[j] < num[p] && num[p] < num[s] && num[s] < num[i]) {return true;}}}return false;}int main()
{int CaseNum;scanf("%d",&CaseNum);while(CaseNum--){scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d",&num[i]);}if(solve()) cout<<"YES\n";else{reverse(num+1,num+m+1);if(solve()) cout<<"YES\n";else cout<<"NO\n";}}
}
/*
3
6
10 30 60 40 20 50
8
30 40 10 20 80 50 60 70
4
1 2 20 9YES
NO
NO*/

Hit

这篇关于1618 - Weak Key【贪心】【搜索】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---