当前位置:首页 > 题解目录 > 正文内容

【题解】数字的选择

亿万年的星光3年前 (2022-10-21)题解目录1882

【题目描述】

有n个非负整数,请从这n个非负整数中,选出m个数,在不改变m个数的顺序的情况下,构成一个新数列,要求该数列的中相邻两个数的差值绝对值的和尽可能小。

请问,这个最小的差值绝对值的和是多少?

比如:有5个数是2 1 8 5 9,如果从中选3个数,不改变顺序的情况下,要求相邻2个数的差值绝对值的和最小,选数方法可以是:2 1 5,差值绝对值的和是|1-2|+|5-1|=5。

【输入描述】

第1行输入2个整数,分别是n和m。(2≤m≤n≤100)

第2行,有n个非负整数,数字之间用空格隔开。

【输出描述】

按题意输出最小的差值绝对值的和。(本题保证计算出来的结果,在int的范围内)

【样例输入】

5 3
2 1 8 5 9

【样例输出】

5


【参考答案】

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n,m;
int a[N],f[N][N];
 
int main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			f[i][j] = 1e9;
		}
	}
	
	int ans = 1e9;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= min(i,m);j++){
			if(j == 1){
				f[i][j] = 0;
				continue;
			}
			for(int k = j-1;k < i;k++){
				f[i][j] = min(f[i][j],f[k][j-1]+abs(a[k]-a[i]));
			}
			
			if(j == m) ans = min(ans,f[i][j]);
		}
	}
	
//	for(int i = 1;i <= n;i++){
//		for(int j = 1;j <= m;j++){
//			cout<<f[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	
	cout<<ans;
	return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】奇偶校验

【题目描述】奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数 是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶校验。现在给...

【题解】苯小猴

【题目描述】笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设maxn是单词中出现次数最...

【题解】BFS、DFS——走迷宫问题

【题目描述】给定一个 n×m的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,...

【题解】游览动物园

【题目描述】动物园有很多游览区,小红已经在动物园的一个游览区游览,突然接到电话,要半个小时内到动物园外面跟一个朋友见面。半个小时小红只够游览完当前区域之后,游览一个最近的景区。已知从一个游览区域只能沿...

字符串反连接

【题目描述】写一函数,使输入的一个字符串按反序存放,在主函数中输入并输出反序后的字符串(不包含空格)。【输入描述】一行字符【输出描述】逆序后的字符串【样例输入】123456abcdef【样例输出】fe...

2020CSPJ-直播获奖

【题目描述】NOI2130 即将举行。为了增加观赏性,CCF 决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为w%,即当前排名前 w% 的选手的最低成绩就是即时的分数线...