rt,这是我的代码:
//dp[i] = min(dp[j]+(h[i]-h[j])^2+C)
//dp[i] = dp[j]+(h[i]-h[j])^2+C
//dp[i] = dp[j]+h[i]^2-2*h[i]*h[j]+h[j]^2+C
//dp[i] = dp[j]+h[i]^2-2*h[i]*h[j]+h[j]^2+C
//dp[j]+h[j]^2 = 2*h[i] * h[j] + dp[i]-h[i]^2-C
// y = k * x + b
//启动!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,C,a[200001],dp[200001],q[200001];
int X(int j){
return a[j];
}
int Y(int j){
return dp[j]+pow(a[j],2);
}
double query(int i,int j){
return 1.0*(Y(j)-Y(i))/(X(j)-X(i));
}
signed main(){
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>a[i];
int h=1,t=1;
q[1]=1;
for(int i=2;i<=n;i++){
while(h<t&&query(q[h],q[h+1])<=2*a[i]) h++;
dp[i]=dp[q[h]]+pow(a[i]-a[q[h]],2)+C;
while(h<t&&query(q[t-1],i)<=query(q[t-1],q[t])) t--;
q[++t]=i;
}
cout<<dp[n];
}
原代码:
int query(int i,int j){
return (Y(j)-Y(i))/(X(j)-X(i));
}