首页 > 代码库 > 51nod1241(连续上升子序列)
51nod1241(连续上升子序列)
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241
题意：中文题诶～
思路：通过观察我们不难发现就是找连续上升子序列，答案就是n-最长连续上升子序列长度；
注意：我们要找的是3, 4, 5, 6这样的连续上升子序列，而非1, 3, ５, 9 这样的上升子序列，因为两个连续的数之间如果有其他数我们可以直接移除，但是如果不连续的话我们无法直接加进去。。。
代码：
1 #include <iostream>
2 #define MAXN 50010
3 using namespace std;
4
5 int dp[MAXN];
6
7 int main(void){
8 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
9 int n, x, ans=0;
10 cin >> n;
11 for(int i=0; i<n; i++){
12 cin >> x;
13 dp[x]=dp[x-1]+1;
14 ans=max(ans, dp[x]);
15 }
16 cout << n-ans << endl;
17 return 0;
18 }
51nod1241(连续上升子序列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。