【题目描述】

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

(adsbygoogle = window.adsbygoogle || []).push({});