ATCoder DP Contest Z题：三分法替代凸包优化的解法是否正确？

题目为AtCoder DP系列的Z题，已知可通过DP+凸包优化求解，尝试用三分法替代凸包优化，给出如下代码，询问该解法是否正确：

#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 0<=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];
}

解法正确性分析 #

该解法不正确，核心原因是三分法的适用前提不满足：

1. 三分法的依赖条件：单峰函数 #

三分法能正确找到函数极值的前提是，目标函数是单峰函数（即先严格递减后严格递增，或先严格递增后严格递减）。但在本题中，当输入的a数组不单调时，对于部分i，函数f(j) = dp[j] + (a[i]-a[j])² + c（即从状态j转移到i的成本）的图像不满足单峰性，此时三分法会错误地缩小搜索范围，错过真正的最小值点。

2. 反例验证 #

构造如下测试用例：

• n=5，c=1
• a = [20, 1, 2, 3, 4]

计算过程：

• dp[0] = 0
• dp[1] = dp[0] + (1-20)² +1 = 362
• dp[2] = min(dp[0]+(2-20)²+1, dp[1]+(2-1)²+1) = min(325, 364) = 325
• dp[3] = min(dp[0]+(3-20)²+1, dp[1]+(3-1)²+1, dp[2]+(3-2)²+1) = min(290, 367, 327) = 290
• 对于i=4，f(j)的值为：
  • j=0: 0 + (4-20)²+1 = 257（最优解）
  • j=1: 362 + (4-1)²+1 = 372
  • j=2: 325 + (4-2)²+1 = 330
  • j=3: 290 + (4-3)²+1 = 292

此时f(j)的变化趋势是：257 → 372（递增）→ 330（递减）→ 292（递减），完全不满足单峰性。

三分法的执行过程：

1. 初始lo=0，hi=3
2. 计算diff=1，m1=1，m2=2
3. 比较f(1)=372和f(2)=330，因为372>330，将lo更新为1
4. 此时搜索范围缩小到j=1~3，最终比较这三个值得到最小值292，但正确的最小值是257（对应j=0）

可见，三分法错误地排除了最优解所在的区间，导致dp[4]计算错误。

3. 额外说明 #

即使a数组单调，三分法的时间复杂度为O(n log n)，虽然能通过部分测试用例，但原题中a数组可以是任意值，因此该解法无法处理所有合法输入，不具备通用性和正确性。

内容的提问来源于stack exchange，提问作者Subhram Subhrajyoti Rana