hdu 3507 Print Article（dp+斜率优化）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3507

 

题解：显然这题的递推很容易得到

dp[i]=dp[j]+(sum[i]-sum[j])^2+m

显然这样的要两个for肯定超时。这里就要用到斜率优化。

不妨设k<j<i;

显然这里j是最优解所以dp[j]+m+(sum[i]-sum[j])^2<dp[k]+m+(sum[i]-sum[k])^2化简一下就是

(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]，设yj = dp[j]+num[j]^2,yk=dp[k]+num[k],xj=2*num[j],xk=2*num[k]

那么就是(yj-yk)/(xj-xk)<sum[i];这时候是j为k道i之间的最优解

不妨设g[j , k]=(yj-yk)/(xj-xk)

依旧设k<j<i;

如果g[i,j]<g[j,k]，那么j点便永远不可能成为最优解

当g[i,j]<sum[i]，那么就是说i点要比j点优，排除j点。

当g[i,j]>=sum[i]，那么j点此时是比i点要更优，但是同时g[j,k]>g[i,j]>sum[i]。这说明还有k点会比j点更优，同样排除j点。

所以只有在g[i,j]>=g[j,k]时j才有可能是最优解

那么这样就可以利用单调队列来优化了。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int M = 5e5 + 10;
ll a[M] , dp[M] , sum[M];
int q[M] , n , m;
ll get_up(int i , int j) {
    return (dp[i] + sum[i] * sum[i]) - (dp[j] + sum[j] * sum[j]);
}
ll get_down(int i , int j) {
    return (2 * sum[i] - 2 * sum[j]);
}
ll get_dp(int i , int j) {
    return dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;
}
int main() {
    while(scanf("%d%d" , &n , &m) != EOF) {
        sum[0] = dp[0] = 0;
        for(int i = 1 ; i <= n ; i++) {
            scanf("%lld" , &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        int head = 0 , tail = 0;
        q[tail++] = 0;
        for(int i = 1 ; i <= n ; i++) {
            while(head + 1 < tail && get_up(q[head + 1] , q[head]) <= sum[i] * get_down(q[head + 1] , q[head])) head++;
            dp[i] = get_dp(i , q[head]);
            while(head + 1 < tail && get_up(i , q[tail - 1]) * get_down(q[tail - 1] , q[tail - 2]) <= get_up(q[tail - 1] , q[tail - 2]) * get_down(i , q[tail - 1]))
                tail--;
            q[tail++] = i;
        }
        printf("%lld\n" , dp[n]);
    }
    return 0;
}