首页 > 代码库 > Almost Sorted Array---hdu5532（j简单dp）
Almost Sorted Array---hdu5532（j简单dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5532
题意：问一个含有n个数的序列，删除一个数后是否有序(递增或递减都可以)
我们只要求一下最长上升子序列或者最长下降子序列是否大于等于n-1即可；
时间复杂度n*log(n);
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>#include<set>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define N 100005#define INF 0x3f3f3f3ftypedef long long LL;int n, a[N], dp[N];int solve1(){ for(int i=0; i<=n; i++) dp[i] = INF; int ans = 0; for(int i=1; i<=n; i++) { int pos = upper_bound(dp, dp+n, a[i]) - dp; dp[pos] = min(dp[pos], a[i]); ans = max(ans, pos); } return ans+1;}int solve2(){ for(int i=0; i<=n; i++) dp[i] = INF; int ans = 0; for(int i=n; i>=1; i--) { int pos = upper_bound(dp, dp+n, a[i]) - dp; dp[pos] = min(dp[pos], a[i]); ans = max(ans, pos); } return ans+1;}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]); int ans1 = solve1(); int ans2 = solve2(); if(ans1 >= n-1 || ans2 >= n-1) puts("YES"); else puts("NO"); } return 0;}
Almost Sorted Array---hdu5532（j简单dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。