输入正整数d和n个正整数x1,x2,…xn,可以修改除了x1和xn的其他数,要求修改后序列满足相邻2个|xi - xi-1| <=d,修改的代价就是两数相减绝对值,问最小代价。无解输出-1。用c++实现
时间: 2024-03-25 21:38:10 浏览: 16
好的,以下是 C++ 的实现代码:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 105;
int d, n, x[MAXN];
int dp[MAXN][MAXN];
int main() {
cin >> d >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
// 初始化
for (int j = 1; j <= 100; j++) {
dp[2][j] = abs(x[2] - j);
}
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= 100; j++) {
dp[i][j] = INF;
for (int k = 1; k <= 100; k++) {
if (abs(j - k) <= d) {
dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(x[i] - j));
}
}
}
}
int ans = INF;
for (int j = 1; j <= 100; j++) {
if (abs(j - x[n]) <= d) {
ans = min(ans, dp[n][j]);
}
}
cout << (ans == INF ? -1 : ans) << endl;
return 0;
}
```
其中,我们将数值范围限制为 1 ~ 100,因为题目并没有给出数值范围。如果需要更大的数值范围,可以根据具体情况进行修改。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)