HDU-3507Print Article 斜率优化DP

时间：2024-05-01 16:08:19

学习:https://blog.****.net/bill_yang_2016/article/details/54667902

HDU-3507

题意：有若干个单词，每个单词有一个费用，连续的单词组合成一块有花费：(∑Ci)^2+M，问如何分单词，使得这些花费和最小。

思路：dp，但是由于数据n = 5e5，所以需要利用斜率优化dp，维护一个下凸包。

大佬的分析：http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html；

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <list>

#include <cstdlib>

#include <iterator>

#include <cmath>

#include <iomanip>

#include <bitset>

#include <cctype>

#include <deque>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

#define fi first

#define se second

#define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

// #define _DEBUG;         //*//

#ifdef _DEBUG

freopen("input", "r", stdin);

// freopen("output.txt", "w", stdout);

#endif

/*-----------------show time----------------*/

            const int maxn =;

            ll dp[maxn],a[maxn];

            ll sum[maxn];

            int q[maxn];

        double slope(ll j, ll k ){  //计算斜率。

                if(sum[k]==sum[j])return 0.0;

                return(dp[j] + 1ll*sum[j] * sum[j] - (dp[k] + 1ll*sum[k]*sum[k]) )*1.0/( * (sum[j] - sum[k]));

        }

int main(){

            int n,m;

            while(~scanf("%d%d", &n, &m)){

                sum[] = ;

                for(int i=; i<=n; i++){

                    scanf("%lld", &a[i]);

                    sum[i] = sum[i-] + a[i];

                }

                int le = ,ri = ;

                q[] = ;

                dp[] = ;

                for(int i=; i<=n; i++){

                    while(le < ri && slope(q[le] , q[le+]) < sum[i]) le++; //维护不等式成立的条件

                    dp[i] = dp[q[le]] + 1ll*(sum[i] - sum[q[le]]) *  (sum[i] - sum[q[le]]) + m;

                    while(le < ri && slope(q[ri] , q[ri-]) >= slope(q[ri],i))ri--;//斜率优化，删点。

                    q[++ri] = i;

                }

                printf("%lld\n", dp[n]);

            }

    return ;

}

HDU-3507

相关文章