首页 > 其他 > 详细

51nod1241(连续上升子序列)

时间:2017-01-24 19:06:35      阅读:216      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241

 

题意:中文题诶~

 

思路:通过观察我们不难发现就是找连续上升子序列,答案就是n-最长连续上升子序列长度;

注意:我们要找的是3, 4, 5, 6这样的连续上升子序列,而非1, 3, 5, 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(连续上升子序列)

原文:http://www.cnblogs.com/geloutingyu/p/6347665.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!