ATCoder教育DP竞赛Z-frog 3(通过三元搜索而不是凸包优化)

Question

以下是问题链接：https://atcoder.jp/contests/dp/tasks/dp_z

是的，这可以通过DP和凸包优化技巧来解决。但是，我们可以提供一个时间因子o(logN(，而不是凸包技巧。所以我想用三元搜索来代替上面的优化。

这是我的代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int imax=2*1e5+10;
ll dp[imax], a[imax], n, c;
ll sqr(ll a){
    return a*a;
}
ll getCost(int i, int j){
    return dp[i]+sqr(a[j]-a[i])+c;
}
int getMinIndex(int lo, int mid, int hi,int i){
    vector<pair<ll,int>> b={{getCost(lo,i),lo},{getCost(mid,i),mid},{getCost(hi,i),hi}};
    sort(b.begin(), b.end());
    return b[0].second;
}
// ternary search over index 'j' where o<=j<i
int getMinCostFor(int i){
    int lo=0, hi=i-1;
    if(lo==hi)return getCost(lo,i);
    while(hi>lo+2){
        int diff = (hi-lo)/3;
        int m1=lo+diff;
        int m2=lo+2*diff;
        if(getCost(m1,i)>getCost(m2,i))lo=m1;
        else hi=m2;
    }
    return min({getCost(lo,i),getCost(lo+1,i),getCost(hi,i)});
}
int main() {
    cin>>n>>c;
    for(int i=0;i<n;i++) cin>>a[i];
    dp[0]=0;
    for(int i=1;i<n;i++)
        dp[i]=getMinCostFor(i);
    cout<<dp[n-1];
}

有人能告诉我这是不是正确的方法吗？如果不是，请提供一个有效的理由。

Answer 1

不，我不相信可以保证我们的距离函数是单峰的。虽然我们可以确保我们的dp对于高于或低于它的石头集是单调递减的，但只要我们在阵列中迭代，并且我们知道，当从高度最接近当前石头的石头迭代到距离当前石头高度最远的石头时，我们不能保证这两个距离的总和是单峰的，因为第二个函数的增长速率小于第一个函数在潜在的不止一个点上的增长速率，反之亦然。