2019牛客暑期多校第十场 J.Wood Processing

题意：

(nleq5000)个宽度为(w_i),高为(h_i) 的木块，要求分成(k)组，对于每组内的所有木块，高度都变为组内最低木块的高度，宽度保持不变，求变化的最小面积。

思路：

先按照高度从大到小排个序。

其实就相当于将这些序列cut成k份，每份有一个代价，要求总代价最小。

每一份中的代价取决于什么呢？

这一份木板中最矮的那一个的高度。
（其他木板的高度与最矮的高度之差）*其他木板的宽度。

知道这些之后，就可以开始(dp)了。

这时候可以设(f(i,j))表示考虑到第(i)块木板，切成了(j)份的最小代价是多少。

但是这样不太好，因为每一份中木板的高度不尽相同，所以势必让转移方程变复杂。

所以换一个思路，设(f(i,j))表示考虑到第(i)块木板，切了(j)份之后最大的面积是多少。

[f(i,j)=max(f(k,j-1)+(sW(i)-sW(k)*h(i)) ]

其中(0leq k< i)，(sW)表示宽度的前缀和。此时答案为(tot-f(n,k))，其中(tot)表示木板总面积。

由于需要枚举(i,j,k)，时间复杂度(O(n^3))，无法通过。

展开上式

[f(i,j)=sW(i)h(i)+max{f(k,j-1)-sW(k)*h(i)} ]

去掉(max:)

[f(i,j)=sW(i)h(i)+f(k,j-1)-sW(k)*h(i) ]

[f(k,j-1)=sW(k)*h(i)+[f(i,j)-sW(i)h(i)] ]

这样的话就变成斜率(dp)的形式了。

我们发现转移方程成了以(sW(k))为自变量，(f(k,j-1))为因变量，(h(i))为斜率，(f(i,j)-sW(i)h(i))为截距的直线。

当截距最大时，(f(i,j))取到最大。

所以用单调队列维护一个上凸壳。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5000+10;
typedef long long ll;
struct Node{
    ll w, h;
}a[maxn];
bool cmp(Node a, Node b){
    return a.h > b.h;
}

int n, k;
int q[maxn];
ll sum[maxn];
ll f[maxn][maxn];
ll area;

long double slope(int x,int y,int p){
    return (long double)1.0*(f[x][p-1]-f[y][p-1])/(sum[x]-sum[y]);
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].w, &a[i].h);
    sort(a+1, a+1+n, cmp);
    for(int i = 1; i <= n; i++)
    {
        sum[i] = sum[i-1]+a[i].w;
        area += a[i].h*a[i].w;
    }


    int hh, tt;
    //队列中数据单调递减
    for(int j = 1; j <= k; j++)
    {
        hh = 1, tt = 1;
        for(int i = 1; i <= n; i++)
        {
            while(hh < tt && slope(q[hh],q[hh+1],j) >= a[i].h) hh++;
            int t = q[hh];
            f[i][j] = f[t][j-1]+(sum[i]-sum[t])*a[i].h;
            while(hh < tt && slope(q[tt],q[tt-1],j) <= slope(q[tt],i,j)) tt--;
            q[++tt] = i;
        }
    }
    cout << (area-f[n][k]) << endl;
    return 0;
}