题解 P5929 【[POI1999]地图】

youyou2007 · 2020-10-23 11:32:46 · 题解

一、思路

1、朴素转移

这题题目都讲了区间，明显的区间DP......

令f[i][j] 表示考虑了前i 个区域，已经用了j 种颜色的最小误差

则枚举 k, f[i][j] 一定是从前k个区间的最小值再加上从k+1 至 i 的区间误差，

状态转移方程式：f[i][j] = min(f[i][j], f[k][j - 1] + color(k + 1, i)) ，其中color 即为区间误差之和。

时间复杂度：O(N ^ 3M)

很明显，这个巨大的复杂度会T飞，所以需要一些优化

2、求值优化

再思考优化color ，可以先前缀和sum 求出每一段的人口数，而中位数即为排好序后中间两个数的平均数。

所以区间误差之和不难得出，可以得到以下O(1) 的柿子：

二、code

注意开始需要先排序，这样求中位数可以优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
const int M = 15;
int n, m;
int f[N][M], sum[N], a[N];
int color(int l, int r)
{
    int mid = (l + r) / 2;//求中位数的位置
    return a[mid] * (mid - l) - sum[mid - 1] + sum[l - 1] - a[mid] * (r - mid) + sum[r] - sum[mid]; //O(1)优化
}              
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];//前缀和预处理
    }
    memset(f, 0x3f, sizeof f);//开始全赋最大值
    f[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            for(int k = 0; k < i; k++)
            {
                f[i][j] = min(f[i][j], f[k][j - 1] + color(k + 1, i));//转移方程
            }
        }       
    }
    cout << f[n][m];
    return 0;
}