第一行输入一个整数
代表同学数量。
第二行输入
个整数
代表每一位同学的身高。
输出一个整数,代表最少需要出列的同学数量。
8 186 186 150 200 160 130 197 200
4
在这个样例中,有且仅有两种出列方式,剩下的同学分别为
和
。
#include <string.h> #include <stdio.h> #include <stdlib.h> #define max(a, b) ((a) > (b) ? (a) : (b)) void GetIncreaseLen(int dp_increase[], int num[], int len) { dp_increase[0] = 1; for(int i = 1; i < len; i++){ dp_increase[i] = 1; for(int j = 0; j < i; j++){ if(num[i] > num[j]){ int temp = dp_increase[j] + 1; dp_increase[i] = max(temp, dp_increase[i]); } } } } void GetDecreaseLen(int dp_decrease[], int num[], int len) { dp_decrease[len-1] = 1; for(int i = len-2; i >= 0; i--){ dp_decrease[i] = 1; for(int j = len-1; j > i; j--){ if(num[i] > num[j]){ int temp = dp_decrease[j] + 1; dp_decrease[i] = max(temp, dp_decrease[i]); } } } } int main() { int n; scanf("%d", &n); int num[n]; for(int i = 0; i < n; i++){ scanf("%d", &num[i]); } int res = 0; if(n == 1){ res = 0; }else if(n == 2){ res = 1; }else{ int dp_increse[n]; int dp_decrese[n]; int maxLen = 1; GetIncreaseLen(dp_increse, num, n); GetDecreaseLen(dp_decrese, num, n); for(int i = 0; i < n; i++){ if(dp_increse[i] == 1 || dp_decrese[i] == 1){ continue; } maxLen = max(maxLen, (dp_decrese[i]+dp_increse[i]-1)); } res = n - maxLen; } printf("%d\n", res); return 0; }
#include <stdio.h> #include <stdlib.h> void search(int* hight, int* top, int* len) { static int sta[1500] = {}; for (int x = *top; x >= 0; x--) if (*hight > sta[x] || !(*hight | sta[x])) { sta[x + 1] = *hight; *len += x; *top += x == *top ? 1 : 0; break; } } int main() { int n, top = 0, maxnum = 0; scanf("%d", &n); int len[3000]={}, arr[n]; for (int i = 0; i < n; i++) { //求左端不下降子序列长度 scanf("%d", arr + i); search(arr + i, &top, len + i); } top = 0; for (int i = n - 1; i >= 0; i--) { //求右端不下降子序列长度 search(arr + i, &top, len + i); if (len[i] + 1 > maxnum) maxnum = len[i] + 1; } printf("%d\n", n - maxnum); //输出结果 }
#include <stdio.h> #include <string.h> #define MAXN 3000 static int N; static int tall[MAXN]; static int dpl[MAXN], dpr[MAXN]; int max(int a, int b) { return a > b ? a : b; } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &tall[i]); } for (int i = N - 1; i >= 0; i--) { for (int j = N - 1; j > i; j--) { dpr[i] = tall[j] < tall[i] ? max(dpr[i], dpr[j] + 1) : dpr[i]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { dpl[i] = tall[j] < tall[i] ? max(dpl[i], dpl[j] + 1) : dpl[i]; } } int resK = 0; for (int i = 0; i < N; i++) resK = max(resK, dpr[i] + dpl[i] + 1); printf("%d", N - resK); return 0; }
#include <stdio.h> #include <string.h> int main(){ int N;scanf("%d",&N); int a[N];int max; for(int i=0;i<N;i++){ scanf("%d",&a[i]); } //逆序遍历,以当前元素为基准,记录其右边的最大严格递减序列的元素个数 int dp_r[N];memset(dp_r,0,sizeof(dp_r)); for(int i=N-2;i>-1;i--){ max=-1; for(int j=i+1;j<N;j++){ if(a[i]>a[j] && dp_r[j]>max){ max=dp_r[j]; dp_r[i]=dp_r[j]+1; } } } //顺序遍历,以当前元素为基准,记录其左边的最大严格递增序列的元素个数 int dp_l[N];memset(dp_l,0,sizeof(dp_l)); for(int i=1;i<N;i++){ max=-1; for(int j=i-1;j>-1;j--){ if(a[i]>a[j] && dp_l[j]>max){ max=dp_l[j]; dp_l[i]=dp_l[j]+1; } } } //遍历整个数组,计算当前元素dp_r[i]+dp_l[i]的大小,计算最大值 for(int i=0;i<N;i++){ if(dp_r[i]+dp_l[i]>max){ max=dp_r[i]+dp_l[i]; } } printf("%d",N-max-1); }
#include <stdio.h> #include <string.h> int search(int* a,int key,int high){//二分查找 int low=0,mid; while(low<=high){ mid=(low+high)/2; if(a[mid]==key){ return mid; } else if(a[mid]>key){ high=mid-1; } else{ low=mid+1; } } if(a[mid]>key){ return mid; } else{ return mid+1; } } int main(){ int N;scanf("%d",&N); int a[N];int b[N];memset(b,0,sizeof(b));//辅助数组 for(int i=0;i<N;i++){ scanf("%d",&a[i]); } int max=0;int p; //顺序遍历,以当前元素为基准,记录其左边的最大严格递增序列的元素个数 int dp_l[N];dp_l[0]=0; b[max]=b[0]=a[0]; for(int i=1;i<N;i++){ if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换 dp_l[i]=0; b[0]=a[i]; } else if(a[i]>b[max]){//原数组元素值超过辅助数组上界,将其插入后形成新的上界 dp_l[i]=++max; b[max]=a[i]; } else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换 p=search(b,a[i],max); dp_l[i]=p; b[p]=a[i]; } } max=0; //逆序遍历,以当前元素为基准,记录其右边的最大严格递减序列的元素个数 int dp_r[N];dp_r[N-1]=0;memset(b,0,sizeof(b)); b[max]=b[0]=a[N-1]; for(int i=N-2;i>-1;i--){ if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换 dp_r[i]=0; b[0]=a[i]; } else if(a[i]>b[max]){//原数组元素值超过辅助数组上界,将其插入后形成新的上界 dp_r[i]=++max; b[max]=a[i]; } else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换 p=search(b,a[i],max); dp_r[i]=p; b[p]=a[i]; } } //遍历整个数组,计算当前元素dp_r[i]+dp_l[i]的大小,计算最大值 for(int i=0;i<N;i++){ if(dp_r[i]+dp_l[i]>max){ max=dp_r[i]+dp_l[i]; } } printf("%d",N-max-1); }
#include <stdio.h> #define N 3000 int main() { int height[N],left[N]={0},right[N]={0},n,i,j,flag,max=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&height[i]); //从左到右寻找递增子列 for(i=0;i<n;i++) { flag=0; if(i==0) left[i]=1; else { for(j=0;j<i;j++) { if(height[i]>height[j]&&left[j]+1>left[i]) { left[i]=left[j]+1; flag=1; } else if(flag==0) left[i]=1; } } } //从右往左寻找递增子列 for(i=n-1;i>=0;i--) { flag=0; if(i==n-1) right[i]=1; else { for(j=n-1;j>i;j--) { if(height[i]>height[j]&&right[j]+1>right[i]) { right[i]=right[j]+1; flag=1; } else if(flag==0) right[i]=1; } } } for(i=0;i<n;i++) left[i]+=right[i]-1; for(i=0;i<n;i++) if(left[i]>max) max=left[i]; printf("%d\n",n-max); return 0; }
#include <stdio.h> #include <stdlib.h> int main() { int num; int i,j; while(scanf("%d",&num)!=EOF) { int *qu=(int *)malloc(sizeof(int)*num); for(i=0;i<num;i++) { scanf("%d",&qu[i]); } int *dp1=(int *)malloc(sizeof(int)*num); for(i=0;i<num;i++) { dp1[i]=1; for(j=0;j<i;j++) { if(qu[j]<qu[i]) { dp1[i]=dp1[i]>(dp1[j]+1)?dp1[i]:(dp1[j]+1); } } } int *dp2=(int *)malloc(sizeof(int)*num); for(i=num-1;i>=0;i--) { dp2[i]=1; for(j=num-1;j>i;j--) { if(qu[j]<qu[i]) { dp2[i]=dp2[i]>(dp2[j]+1)?dp2[i]:(dp2[j]+1); } } } int max=dp1[0]+dp2[0]; for(i=1;i<num;i++) { max=max>(dp1[i]+dp2[i])?max:(dp1[i]+dp2[i]); } printf("%d\n",num-max+1); } return 0; }