斜率dp
第一道斜率dp题,终于是理解了斜率dp。点亮技能树,我会变的越来越强的!!
#include<iostream> #include<algorithm> #include<deque> using namespace std; const int max_n = 5e5+100; typedef long long ll; int n,M; ll a[max_n]; ll sum[max_n]; deque<int> que; ll dp[max_n]; bool check(ll k){ int a = que[0],b=que[1]; ll x1 = sum[a],y1 = dp[a]+sum[a]*sum[a]; ll x2 = sum[b],y2 = dp[b]+sum[b]*sum[b]; if (x1<x2)swap(x1,x2),swap(y1,y2); return (y1-y2)<=k*(x1-x2); } bool check2(int i){ int a = que.back(),b=que[que.size()-2]; ll x1 = sum[a],y1 = dp[a]+sum[a]*sum[a]; ll x2 = sum[b],y2 = dp[b]+sum[b]*sum[b]; ll x3 = sum[i],y3 = dp[i]+sum[i]*sum[i]; if ((x1-x2)*(x3-x2)<0)swap(x1,x2),swap(y1,y2); return (y3-y2)*(x1-x2)<=(y1-y2)*(x3-x2); } int main(){ while(~scanf("%d %d",&n,&M)){ que.clear(); for (int i=1;i<=n;++i)scanf("%lld",&a[i]); for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i]; que.push_back(0); for (int i=1;i<=n;++i){ ll k = 2*sum[i]; while (que.size()>=2&&check(k))que.pop_front(); int j = que.front(); dp[i]=dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+(ll)M; while (que.size()>=2&&check2(i))que.pop_back(); que.push_back(i); }printf("%lld\n",dp[n]); } }