划分序列最小化代价 - 算法题解

题目描述

给定一个长度为 'n' 的序列 'h_i',你需要把这个序列划分成 'k' 个连续的子序列,保证每个子序列的长度不小于 '1' 且不大于 'n/k'。

定义一个子序列的价值为这个子序列中最大值减去最小值的差,你需要最小化这 'k' 个子序列价值之和。输出最小的这个和。

输入格式

第一行两个整数 'n,k',表示序列的长度和子序列的个数。

第二行有 'n' 个整数 'h_i',表示这个序列。

输出格式

输出一行一个整数,表示最小的 'k' 个子序列价值之和。

输入输出样例

输入 #1

5 2
1 2 3 4 5

输出 #1

1

输入 #2

8 4
4 4 4 4 4 4 4 4

输出 #2

0

题解

思路:

'f[i][j]' 表示前 'i' 个数分成 'j' 个子序列的最小代价。状态转移方程如下:

'f[i][j] = min(f[i][j], f[k][j - 1] + cost(k + 1, i))'

其中,'cost(l, r)' 表示将区间 '[l, r]' 分成一段的代价,即 max(h[l], h[l + 1], …, h[r]) - min(h[l], h[l + 1], …, h[r])。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 50;
const int INF = 1e9 + 7;
#define fer(i, a, b) for(int i = a; i <= b; ++i)

int n, k;
int h[N], f[N];
int main()
{
	cin >> n >> k;
	fer(i, 1, n)
		cin >> h[i];
	fer(i, 1, n)
		f[i] = INF;
	for(int i = 1; i <= n; ++i)
	{
		
	}
}

时间复杂度 'O(n^3k)'。

划分序列最小化代价 - 算法题解

原文地址: https://www.cveoy.top/t/topic/ndSk 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录