自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:46:32，当前版本为作者最后更新于2023-04-17 23:07:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

首先按照编号从小到大地考虑机器，可以发现当考虑到第 $i$ 台机器时，生产的钻石不是 $2^i$ 倍数的情况一定不优。那么想到 dp，设 $f(i,j)$ 表示前 $i$ 台机器生产了 $j\times 2^i$ 个钻石的最小花费，暴力实现的时间复杂度是指数级的，下面我们考虑优化。

第一个优化，根据 $a_i,b_i$ 的范围我们容易发现每台机器被启动的次数一定不会太多。具体来说启动 $k$ 次的花费是 $k\times a_i+{k\times (k-1)\over 2}\times b_i\geq {k\times(k+1)\over 2}$，而答案最大也只能是 $a_n$，于是 $k\leq \sqrt {2a_n}$，于是 $j$ 最大只需枚举到 $k\times{\sum_{p=1}^i 2^p\over 2^i}=2\sqrt {2a_n}$。此时我们优化到了 $O(n\times a_n)$。

第二个优化，再考虑能否快速转移。我们列式子有 $f_{i,j}=\min \{ f_{i-1,2\times k}+(j-k)\times a_i+{(j-k-1)(j-k)\over 2}\times b_i\}$，而在每一轮转移中与 $i$ 相关的东西都是固定的，所以转化成 $g_j=\min \{h_k+(j-k)\times a+{(j-k-1)(j-k)\over 2}\times b\}$ 这种形式。那么发现可以斜率优化，横坐标单增，使用单调队列维护下凸壳。总时间复杂度优化到了 $O(n\sqrt {a_n})$，可以通过本题。

代码

/*
  author: PEKKA_l  
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define int long long

int n,a[1005],b[1005],dp[9005],g[9005],head,tail,q[9005];

int gety(int x,int k) {return g[k]+k*(k+1)*b[x]/2-a[x]*k;}

signed main()
{
	cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=0;i<=9000;i++) dp[i]=a[1]*i+b[1]*(i-1)*i/2;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=4500;j++) {g[j]=dp[j<<1]; g[j+4500]=100000000000000000;} head=tail=1;
		for(int j=1;j<=9000;j++)
		{
			while(head<tail&&(double)(gety(i,q[tail])-gety(i,q[tail-1]))/(q[tail]-q[tail-1])>=(double)(gety(i,j)-gety(i,q[tail]))/(j-q[tail])) tail--;
			q[++tail]=j;
			while(head<tail&&b[i]*j>=(double)(gety(i,q[head+1])-gety(i,q[head]))/(q[head+1]-q[head])) head++;
			dp[j]=g[q[head]]+a[i]*(j-q[head])+(j-q[head]-1)*(j-q[head])*b[i]/2;
		}
	}
	cout<<dp[1]<<endl;
}