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

【题解】数字的选择

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

【题目描述】

有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;
}


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

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

分享给朋友:

相关文章

【题解】分糖果

【题目描述】小A在生日这天收到了哥哥送来的一盒糖果,这盒糖果共有M个,小A要把这盒糖果放到N个盘子中(允许有盘子不放),请问,有多少种不同的放法?请注意:数值相同,顺序不同,我们视为是相同的放法,比如...

【题解】合并有序表

【题目描述】k路归并问题把k个有序表合并成一个有序表。元素共有n个。【输入描述】读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数,表示第i个序列。总数小于100000。【输出描述】输...

【题解】数学游戏

【题目描述】Kri 喜欢玩数字游戏。 一天,他在草稿纸上写下了t 对正整数(x,y) ,并对于每一对正整数计算出了z=x*y*gcd(x,y);可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一...

【题解】剔除相关数

【题目描述】一个数与另一个数如果含有相同数字和个数的字符,则称两数相关。现有一堆乱七八糟的整数,里面可能充满了彼此相关的数,请你用一下手段,自动地将其剔除。【输入描述】每组数据前有一个N(<10...

【NOIP2000】计算器的改良

【题目描述】NCL 是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任务:需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手 ZL...

【题解】神奇的fans

【题目描述】传说fans是一个数学天才。在他五岁那年,从一堆数字卡片中选出了4张 卡片:5,7,6,8。这4个数字有什么神秘之处呢?如果把这4张卡片自左往右的排成:5,6,7,8。你就会发现:原来这4...