题目大意:
将 $n$ 个长方形分成若干部分, 每一部分的花费为部分中长方形的 $max_长 * max_宽 $(不是 $max_{长 * 宽}$), 求最小花费
思路:
首先, 可以被其他长方形包含的长方形可以删去
然后我们按长方形的长度从小到大排序 (排序后的长方形的宽度一定是从大到小)
设 $f(i)$ 表示前 i 个长方形的最小花费, 长方形的长和宽分别为 $x(i),y(i)$, 则有方程
$\Large f(i)=min(f(j)+x(i)*y(j+1))$
若对于某个 $i$ 有 $j$ 比 $k$ 优, 则
$f(j)+x(i)*y(j+1)\le f(k)+x(i)*y(k+1)$
化简得 $\frac{f(j)-f(k)}{y(k+1)-y(j+1)}\le x(i)$
维护下凸壳即可
代码
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define maxn 50005
- #define LL long long
- struct Node{
- int x,y;
- bool operator < (const Node& a)const{
- return x!=a.x?x<a.x:y<a.y;
- }
- }a[maxn];
- int n,si,que[maxn],s,t=1;
- LL f[maxn];
- LL calc(int i,int j){
- return (f[i]-f[j]-1)/(a[j+1].y-a[i+1].y)+1;
- }
- void insert(int x){
- while(s<t-1&&calc(x,que[t-1])<=calc(que[t-1],que[t-2]))t--;
- que[t++]=x;
- }
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%d%d",&a[i].x,&a[i].y);
- }
- sort(a+1,a+n+1);
- for(int i=1;i<=n;i++){
- while(si&&a[si].y<=a[i].y)si--;
- a[++si]=a[i];
- }n=si;
- for(int i=1;i<=n;i++){
- while(s<t-1&&calc(que[s+1],que[s])<=a[i].x)s++;
- int w=que[s];
- f[i]=f[w]+1ll*a[i].x*a[w+1].y;
- insert(i);
- }
- printf("%lld",f[n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2616928.html