BZOJ 3156 防御准备 决策单调性斜率优化DP

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

数据范围

1 ≤ n  106,1 ai 10

题解

这大概是第一道我自己做(手推)出来的斜率优化DP?

不多说,直接上推导的过程:

 来保存决策点的队列一直利用斜率维护一个下凸壳就完事了。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<1) + (num<<3) + c - '0';
    return (flag ? -1 : 1) * num;
}
typedef long long ll;
const int maxn = 1e6+5;
ll a[maxn],f[maxn],sum[maxn];
int q[maxn];
double slop(int k,int j){
    return double(f[j] - f[k] + sum[j] - sum[k]) / double(j-k);
}
int n,l,r;
int main(){
    n = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
        sum[i] = sum[i-1] + i;
    }
    for(int i = 1;i <= n;++i){
        while(l < r && slop(q[l],q[l+1]) < i)++l;
        int t = q[l];
        f[i] = f[t] + a[i] + ll(i-t-1)*i - sum[i-1] + sum[t];
        while(l < r && slop(q[r-1],q[r]) > slop(q[r],i))r--;
        q[++r] = i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00