求区间第k小数 数据范围小的时候（100） 考虑dp

华为云挑战赛1001 求前n个区间分成m段的第(len-0.05*len)个小数

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
	char c=0;x=0;
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+c-'0',c=getchar();
}
int t,n,m;
int a[1001],b[1001],ans=0x3f3f3f3f;
int nie[1001],f[101][101];//f[i][j]//i ->n j->m 
inline int cal(int l,int r)
{
	if(l==r)return a[l];//只有一个值的话就是他本身
	for(int i=l;i<=r;i++)
	b[i]=a[i];
	sort(b+l,b+r+1);//排序一下用于求第len-0.05*len小 
	return b[l+nie[r-l+1]-1];//直接返回第几个
}
int main()
{
	for(int i=1;i<=100;i++)
	{
		nie[i]=i-floor(double(i)*0.05);//先预处理i长度区间要求的第k小是第几个
	}
	read(t);
	while(t--)
	{
		memset(f,0x3f3f3f3f,sizeof(f));
		read(n),read(m);
		for(int i=1;i<=n;i++)
			read(a[i]);
		for(int i=1;i<=n;i++)f[i][1]=cal(1,i);//计算1到r分成1个区间的最小值
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				for(int k=j-1;k<=i-1;k++)
				{
					f[i][j]=min(f[i][j],f[k][j-1]+cal(k+1,i));//转移是 前k个数分成j个区间的对应最小化分位点之和+当前最小段的之和
				}
			}
		}
		cout<<f[n][m]<<endl;
	}
	return 0;
}