划分序列最小化代价 - 算法题解
划分序列最小化代价 - 算法题解
题目描述
给定一个长度为 '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 著作权归作者所有。请勿转载和采集!