关键词：
51nod 1241：特殊的排序
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241
题目大意：给出$n$个数（$1 leqslant a_i leqslant n$），现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成整个排序过程？
DP
显然最少操作数等于$n-|$最长连续子序列$|$.
故定义状态：$dp[i]$表示以$i$结尾的连续子序列长度.
转移方程：$dp[i]=dp[i-1]+1$.
代码如下：
1 #include <iostream> 2 #define N 50005 3 using namespace std; 4 int n,t,dp[N],ans; 5 int main(void){ 6 std::ios::sync_with_stdio(false); 7 cin>>n; 8 for(int i=0;i<n;++i){ 9 cin>>t; 10 dp[t]=dp[t-1]+1; 11 ans=max(ans,dp[t]); 12 } 13 cout<<n-ans; 14 }
51nod1241特殊的排序(代码片段)
本来以为是求LIS，结果发现这样的话就变成随便插入了。。。不过通过这个可以推出正确的思路，就是LIS中还要满足相邻两项(ai)+1==(ai+1)#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#inc... 查看详情
51nod1241特殊的排序(动态规划)
分析:记数组中最长的连续子串长度为maxlen(数值上连续,位置不一定连续,如2134,最长为3).首先可以证明,n-maxlen次操作可以满足条件,如最长子串最后一个为x<n,则把x+1移到最后,如果是x=n,记子串的第一个为y,把y-1移到最前,... 查看详情
51nod1241特殊的排序(代码片段)
【题解】 设满足前后两个元素之差为1的最长上升子序列LIS的长度为m，那么本题的答案即为n-m. 证明： 1，n-m次移动一定可以让序列递增。设LIS的第一个数为i，最后一个数为j，我们按照i-1到1的递减的顺序把这些... 查看详情
51nod1241(连续上升子序列)
...目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241 题意：中文题诶～ 思路：通过观察我们不难发现就是找连续上升子序列，答案就是n-最长连续上升子序列长度；注意：我们要找的是3,4,5,6这样的连续上升子序... 查看详情
1241特殊的排序
1241特殊的排序题目来源：摩根斯坦利的比赛题基准时间限制：1秒空间限制：131072KB一个数组的元素为1至N的整数，现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成... 查看详情
51nod1018排序
给出N个整数，对着N个整数进行排序Input第1行：整数的数量N（1 <= N <= 50000)第2 - N + 1行：待排序的整数（-10^9 <= A[i] <= 10^9） Output共n行，按照递增序输出排序好的数据。&nbs... 查看详情
51nod1019逆序数（归并排序）
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1019题意：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序... 查看详情
51nod1757大灾变(代码片段)
Description原题链接有一棵树，树上有些特殊点，每个不是特殊点的点有一个人，每个人走过一条边的时间为1。现在所有的人要走到特殊点上，每个点可以有多个人，但每条边每1时间只能走一个人。求所有人到达特殊点的最小时... 查看详情
51nod1100(计算几何)
...我们可以用个小技巧来解决这个问题；对这些点用x坐标排序，斜率最大的点一定是排序后相邻的两个点。上述结论的正确性我们不难证明：对于已排序 查看详情
51nod1485字母排序(代码片段)
【题解】 开26棵线段数，记录区间内每种字母的出现次数，修改的时候就用区间设置为一个数操作即可。同时也有平衡树做1#include<cstdio>2#include<algorithm>3#include<cstring>4#defineLLlonglong5#definergregister6#defineN2000107#definel... 查看详情
51nod1097拼成最小的数思路：字符串排序
...p;思路：1.以字符串输入这些整数。 2.对这些字符串排序，排序规则为尽量让能让结果变小的靠前。 代码中有注释，不懂的欢迎在博客中评论问我。 代码：#include<bitsstdc++.h>usingnamespacestd;stringa[10001];//比较规... 查看详情
51nod1107(逆序对数&归并排序)
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107 题意：中文题诶～ 思路：通过题意可以发现对于两点p1(x1,y1)，p2(x2,y2),若x1<x2&&y1>y2则线段p1p2满足要求，那么显然可以先按x值排下序，对应y序列的逆... 查看详情
51nod-01018排序
【算法】排序#include<cstdio>#include<algorithm>usingnamespacestd;intn,a[50010];intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);for(inti=1;i<=n;i++)pr 查看详情
51nod1278相离的圆(二分+排序)
传送门平面上有N个圆，他们的圆心都在X轴上，给出所有圆的圆心和半径，求有多少对圆是相离的。例如：4个圆分别位于1,2,3,4的位置，半径分别为1,1,2,1，那么{1,2},{1,3}{2,3}{2,4}{3,4}这5对都有交点，只有{1,4}是相离的。Input第1行：... 查看详情
51nod1276(xjb)
...屿数目-1，若为极大值点则岛屿数目+1；可以给海面高度排序，海面高度单调时岛屿的状态也是连续的。可以给山峰高度排序，避免对于每一个高度海面都遍历一遍才 查看详情
51nod1182完美字符串字符串排序+哈希
1182 完美字符串题目来源： Facebook Hacker Cup选拔基准时间限制：1 秒空间限制：131072 KB分值: 5 难度：1级算法题 收藏 关注约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母... 查看详情
51nod10903个数和为0(排序+二分）
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1090 首先将序列进行排序，然后根据a+b+c=0,c=-a-b,二分查找c，注意判重，即c>b。时间复杂度O(n*n*logn)。#include<bits/stdc++.h>usingnamespacestd;intn,a[1005];in 查看详情
51nod1010只包含因子235的数(打表+排序+二分）
1010只包含因子2 3 5的数基准时间限制：1秒空间限制：131072KB分值:10难度：2级算法题收藏关注取消关注K的因子中只包含235。满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。所有这样的K组成了一个序列S，现在给出一个数n，求S... 查看详情