P9225 题解

· · 题解

题目分析

首先按照编号从小到大地考虑机器，可以发现当考虑到第 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;
}