(CodeForces

限定：1.给定数字n

2.数组里的数字只能是从1-n中选择

3.要求数字序列的最长上升（递增）子序列和最长递减（下降）子序列最短

结论，当分块数为sqrt(n)的时候最小，分块方法：各个块的内部递增，块的整体递减

比如：对于从1-9这些数字进行分块，789456123的LDS+LIS最小:3+3=6

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=100005;
int n;
int a[maxn];
int main()
{scanf("%d",&n);int k=0;int m=1;int t=sqrt(n);//每块平均长度也是根号nfor(int i=1;i<=(n/t);i++){for(int j=n+1-i*t;j<n+1-(i-1)*t;j++)a[k++]=j;}while(k<n){a[k++]=m++;}for(int i=0;i<n;i++)printf("%d ",a[i]);printf("\n");return 0;
}