Wood Processing

题意:有 n n n块矩形,给出每块矩形底边长和高度,要将 n n n块矩形合并为 k k k块矩形,求最小花费(细节见题目描述)

思路:

  1. 先将矩形从高到低排序,然后处理出 d p dp dp方程转化成的直线方程后所需要的变量
  2. 在做斜率优化DP时,依次枚举合并为 1 1 1块, 2 2 2块,…, k k k块的 d p dp dp值,复杂度为 O ( k n ) O(k*n) O(kn)
  3. 本题维护凸包的小技巧:由于枚举合并为 p p p块的时候只会用到合并为 p 1 p-1 p1块的 d p dp dp值,且假设当前为第 i i i块矩形,则只会考虑 1 1 1 ~ i 1 i-1 i1的合并为 p 1 p-1 p1块的 d p dp dp值,因此可以在内层循环中依次维护下凸包
  4. 下方代码所采用:
    d p dp dp方程为: d p [ i ] = m i n ( d p [ j ] + s [ i ] s [ j ] s w [ j ] ( h [ j ] h [ i ] ) ) dp[i]=min(dp[j]+s[i]-s[j]-sw[j]*(h[j]-h[i])) dp[i]=min(dp[j]+s[i]s[j]sw[j](h[j]h[i]))
    化简后的直线方程为: h [ i ] s w [ j ] + d p [ i ] s [ i ] = d p [ j ] s w [ j ] h [ j ] s [ j ] -h[i]*sw[j]+dp[i]-s[i]=dp[j]-sw[j]*h[j]-s[j] h[i]sw[j]+dp[i]s[i]=dp[j]sw[j]h[j]s[j]
    斜率: k = h [ i ] k=-h[i] k=h[i]
    横坐标: x = s w [ j ] x=sw[j] x=sw[j]
    纵坐标: y = d p [ j ] s w [ j ] h [ j ] s [ j ] y=dp[j]-sw[j]*h[j]-s[j] y=dp[j]sw[j]h[j]s[j]
    截距: b = d p [ i ] s [ i ] b=dp[i]-s[i] b=dp[i]s[i] b b b d p [ i ] dp[i] dp[i]呈正相关,目的是让 d p [ i ] dp[i] dp[i]最小化,即截距最小化)
    (其中 s w [ i ] sw[i] sw[i]为前 i i i块的 w w w的前缀和, s [ i ] s[i] s[i]是前 i 1 i-1 i1块全部与第 i i i块合并的消费)

题目描述

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e3+10;
const int mod = 1e9+7;
const double eps = 1e-7;

struct P{
    ll w, h;
    bool operator < (const P &rhs) const {
        return h>rhs.h;
    }
}p[maxn];

int n, k, head, tail;
ll s[maxn], sw[maxn];
ll dp[2001][maxn], q[maxn]; //其实这里的dp数组的2001可以只写成2,但是后面的代码需要改一些

double slope(int i, int j, int t) {
    ll x1=sw[i], x2=sw[j];
    ll y1=dp[t][i]-sw[i]*p[i].h-s[i];
    ll y2=dp[t][j]-sw[j]*p[j].h-s[j];
    return double(y2-y1)/(x2-x1);
}

int main() {
    //ios::sync_with_stdio(false);
    n=read(), k=read();
    for(int i=1; i<=n; ++i) scanf("%lld%lld", &p[i].w, &p[i].h);
    sort(p+1,p+1+n);
    for(int i=1; i<=n; ++i) s[i]=s[i-1]+sw[i-1]*(p[i-1].h-p[i].h), sw[i]=sw[i-1]+p[i].w;
    for(int i=1; i<=n; ++i) dp[1][i]=s[i];
    for(int t=2; t<=k; ++t) {
        head=0, tail=-1;     
        for(int i=1; i<=n; ++i) {
            while(head<tail&&slope(q[head],q[head+1],t-1)<=-p[i].h) head++;
            int j=q[head];
            dp[t][i]=dp[t-1][j]+s[i]-s[j]-sw[j]*(p[j].h-p[i].h);
            while(head<tail&&slope(q[tail-1],q[tail],t-1)>=slope(q[tail-1],i,t-1)) tail--;
            q[++tail]=i;
        }
    }
    cout<<dp[k][n]<<endl;
}