Print Article

斜率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]);
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
简历当中有水分算不算造假...
点赞 评论 收藏
分享
06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务