EDPC-Z Frog3

読む前の注意はEDPC-Yの記事と一緒

基本的にはA問題と一緒 i個目の柱に到達するのにかかる最小コストを左から作っていけばいい 遷移の時にi-1通り計算していたらTLEするから工夫する

遷移の式を書いていじって見る $dp_i$を$i$番目の柱に乗るのにかかる最小コストとすると

$dp_i=min_{1 \leq j <i}(dp_j+(h_i-h_j)²)+ C$

$=min_{1 \leq j <i}(dp_j+h_j²-2h_ih_j)+h_i²+ C$

$=min_{1 \leq j <i}(f_j(h_i))+h_i²+C$ 　　ただし$f_j(x)=dp_j+h_j²-2h_jx$

よってCHTを使って一次関数の追加と最小値を求めることを交互にやればいい

#include <bits/stdc++.h>
using namespace std;

long long dp[223456];

int main(){
  long long n,c;cin>>n>>c;
  ConvecHullTrick<long long> CHT(1,0);
  for(int i=0;i<n;i++){
    long long h;cin>>h;
    long long res=0;
    if(i)res=CHT.get(h)+h*h+c;
    if(i==n-1)cout<<res<<endl;
    else CHT.add(-2*h,res+h*h);
  }
}

https://atcoder.jp/contests/dp/submissions/11407467