题目:最不上升也不下降序列

思路：

首先，这实际上是一个数学问题。

对于有n个数排列的数列a,我们可以先将其按 / 上升序列或是下降序列其中一种 / 将其来分开看。

例如，对于数列（1，4，3，2，7，6，5），如果选择下降序列，可以看成这样

（【1】，【4，3，2】，【7，6，5】）

我们将其划分为三个下降子序列。

其LIS和LDS之和的最小值为【所有下降子序列中，最长下降子序列的元素个数（LDS）】+【划分出的下降子序列总数（LIS）】

所以求LIS和LDS之和的最小值就是求【划分子序列总数】与【划分出子序列中最长序列元素数】之和的最小值

那么接下来就要找【划分子序列总数】与【划分出子序列中最长序列元素数】二者之间的关系

由于我们只知道数列a的元素个数n与二者都有关，所以要依据a来建立关系

【划分子序列总数】：单个子序列含有元素个数越多，划分子序列总数越少

【划分出子序列中最长序列元素数】：除最长序列外，其余序列含有的元素个数越多，最长子序列元素数越少

所以我们需要找出最长子序列的元素数，再尽可能让其余子序列含有的元素个数接近或等于最大个数

设n=a*b+c (a>=b,c=a%b) //a为最长下降子序列元素个数，b为元素数量为a的子序列个数，如果c不为0，则还需要再增加一个子序列

则最小和为(a+b)，如果c不为0则需再加上1

易证：对于y=xx,(x+t)(x-t)<=x*x(当且仅当t=0时取等)

因此，(a+b)之和固定时，若要使子序列在数量最少的情况下尽可能占有最多的元素，则需使【a=b】（因为a,b为整数，则需在附近取整）

代码(C)：#include<stdio.h> int main() {

int n;
scanf("%d",&n);//输入n 
int x=1;//x用来记录x*x小于等于n的最大数 
while(x*x<n)
{
	x++;
}
if(n==x*x)
{
	int l=x;//l为输出序列时的数字 
	printf("%d",l);
	l--;
	for(int i=2;i<=x;i++)
	{
		printf(" %d",l);
		l--;
	}
	l+=2*x;
	while(l<=n)
	{
		for(int i=1;i<=x;i++)
		{
			printf(" %d",l);
			l--;
		}
		l+=2*x;
	}
}
else
{
	x--;
	int y=x;
	while(x*y<n)
	{
		y++;
	}
	y--;//保证 x*y<n
	int re=n-x*y,s=re;//re为remainer余数的缩写 ，不过当x*(y+1)=n时，re=x;
	//s为输出序列时的数字 
	printf("%d",s);
	s--;
	for(int i=2;i<=re;i++)
	{
		printf(" %d",s);
		s--;
	}
	s=re+x;
	while(s<=n)
	{
		for(int i=1;i<=x;i++)
		{
			printf(" %d",s);
			s--;
		}
		s+=2*x;
	}
}
return 0;

}