请用C++语言动态规划法编程求出最优分段方式及存储位数求图像压缩问题,设输入P=<10,12,15,255,1,2>。代码中请加注释。。
时间: 2024-03-20 18:43:50 浏览: 23
好的,下面是解答:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 1e9; // 定义一个无穷大的常数
int bit(int x) {
int res = 0;
while (x) {
++res;
x /= 10;
}
return res;
}
int main() {
vector<int> P = {10, 12, 15, 255, 1, 2};
int n = P.size();
int m = 3; // 分成3段
int f[n + 1][m + 1];
memset(f, INF, sizeof(f)); // 初始化为无穷大
// 初始化边界情况
for (int i = 1; i <= n; ++i) {
f[i][1] = bit(P[i - 1]);
}
for (int i = 2; i <= n; ++i) {
for (int j = 2; j <= m; ++j) {
for (int k = 1; k < i; ++k) {
f[i][j] = min(f[i][j], f[k][j - 1] + bit(P[k...i-1]));
}
}
}
cout << f[n][m] << endl;
return 0;
}
```
这里采用了三维数组f[i][j],表示将前i个数分成j段的最小存储位数。初始化为无穷大,表示还没有计算过。在计算过程中,枚举前一段的结束位置k,满足P[k+1...i]为一段,然后取最小值。最终的答案为f[n][m],其中n为序列P的长度,m为分成的段数。
相关推荐
![](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)