题解：P9225 「PEOI Rd1」寻宝（treasure）

· · 题解

这题写 dp 还是太小题大做了，我们完全有更容易的做法。

由于我们可以只做一次 n 完成，所以答案的上界是 a_n，而那个式子是个等差数列，所以每个机器最多开动 \sqrt{2a_n}。那就可以暴力贪心了，我们不妨从小到大遍历，若当前在 i，则前面的和如果不是 2^i 的倍数则是不优的（合并到最后会多余，所以我们可以去掉）。然后假设我们已知前面机器 2^{i-1} 的每次开动代价，先两两合并变成 2^i 的代价，再和 i 机器每次代价作归并排序。虽然每次数组和会翻倍，但到下一次数组长度会除以 2。总时间复杂度 O(n\sqrt V)。 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1e9+7;
// head
const int N=1e4+5,INF=1e9;
int a[N],b[N];
int f[N],g[N],f1,g1;
signed main() 
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int mx=sqrt(2.0*a[n]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=f1/2;j++) f[j]=f[2*j-1]+f[2*j];
        int x1=1,x2=1;g1=0;
        while(x1<=f1/2||x2<=mx){
            if(x1<=f1/2&&(x2>mx||f[x1]<=a[i]+(x2-1)*b[i])) g[++g1]=f[x1],x1++;
            else g[++g1]=a[i]+(x2-1)*b[i],x2++;
        }   
        for(int j=1;j<=g1;j++) f[j]=g[j];f1=g1;
    }
    cout<<f[1]<<'\n';
}