使用C语言实现下面动态规划贪心算法题目:有一个长度为n(n <= 240)的正整数,从中取出k(k < n)个数,使剩余的数保持原来的次序不变,求这个正整数经过删数之后最小是多少
时间: 2024-05-16 22:16:37 浏览: 18
这道题可以使用贪心算法和动态规划来解决。下面是使用动态规划的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define INF 0x3f3f3f3f
int n, k;
int a[250], sum[250], dp[250][250];
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (i < j) {
dp[i][j] = INF;
} else if (j == 1) {
dp[i][j] = sum[i];
} else {
dp[i][j] = INF;
for (int p = j-1; p < i; p++) {
dp[i][j] = min(dp[i][j], dp[p][j-1] + sum[i] - sum[p]);
}
}
}
}
printf("%d", dp[n][k]);
return 0;
}
```
主要思路是先用前缀和求出原数组的前缀和,然后用dp[i][j]表示从前i个数中取出j个数的最小值。当i < j时,将dp[i][j]赋为INF,表示无解;当j == 1时,dp[i][j]等于前i个数的和;当j > 1时,枚举最后一个被保留的数的位置p,将原问题分解为dp[p][j-1]和p+1到i这两个子问题,然后用前缀和数组sum求出p+1到i这个子数组的和,最后更新dp[i][j]为dp[p][j-1] + sum[i] - sum[p]。最终答案即为dp[n][k]。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)