Wood Processing
题意:有 n块矩形,给出每块矩形底边长和高度,要将 n块矩形合并为 k块矩形,求最小花费(细节见题目描述)
思路:
- 先将矩形从高到低排序,然后处理出 dp方程转化成的直线方程后所需要的变量
- 在做斜率优化DP时,依次枚举合并为 1块, 2块,…, k块的 dp值,复杂度为 O(k∗n)
- 本题维护凸包的小技巧:由于枚举合并为 p块的时候只会用到合并为 p−1块的 dp值,且假设当前为第 i块矩形,则只会考虑 1 ~ i−1的合并为 p−1块的 dp值,因此可以在内层循环中依次维护下凸包
- 下方代码所采用:
原 dp方程为: dp[i]=min(dp[j]+s[i]−s[j]−sw[j]∗(h[j]−h[i]))
化简后的直线方程为: −h[i]∗sw[j]+dp[i]−s[i]=dp[j]−sw[j]∗h[j]−s[j]
斜率: k=−h[i]
横坐标: x=sw[j]
纵坐标: y=dp[j]−sw[j]∗h[j]−s[j]
截距: b=dp[i]−s[i]( b与 dp[i]呈正相关,目的是让 dp[i]最小化,即截距最小化)
(其中 sw[i]为前 i块的 w的前缀和, s[i]是前 i−1块全部与第 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;
}