icontofig | 发布于 2019-07-07 11:37:58 | 阅读量 116 | DP
发布于 2019-07-07 11:37:58 | DP

数据范围

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;
}

 


内容更新于: 2019-07-07 11:37:58
链接地址: http://blog.leanote.com/post/icontofig/BZOJ-3156

上一篇: 洛谷P1137 旅行计划

下一篇: 网络流24题 之 最长不下降子序列问题 洛谷P2766 分层图

116 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航