斜率优化DP（HYSBZ - 1010 +HDU 3507）

曾经终败给现在 2022-05-18 08:25 209阅读 0赞

思路：这类问题有一个特点，n特别大 1e4以上，而且转移方程必须O（n^2）才能跑完。

通过化简式子可以找到优化的途径。

例如HYSBZ-1010

我们可以写出转移方程![dp\[i\]=min(dp\[j\]+(sum\[i\]-sum\[j\]+i-j-1-L)^2) (i>j>=0)][dp_i_min_dp_j_sum_i_-sum_j_i-j-1-L_2_ _i_j_0]

假设k<j<i,且 j比k更优, 这时候会得到表达式

![dp\[j\]+(sum\[i\]-sum\[j\]+i-j-1-L)^2>=dp\[k\]+(sum\[i\]-sum\[k\]+i-j-1-L)^2][dp_j_sum_i_-sum_j_i-j-1-L_2_dp_k_sum_i_-sum_k_i-j-1-L_2]

设![t=(i-1-L)][t_i-1-L],这时候会化简成

![sum\[i\]>=\{(dp\[j\]-2\*(i-1-M)\*a+a\*a-2\*(i-1-L)\*sum\[j\]+2\*j\*sum\[j\]+sum\[j\]\*sum\[j\])-(dp\[j\]-2\*(i-1-M)\*j+j\*j-2\*(i-1-M)\*sum\[k\]+2\*k\*sum\[k\]+sum\[k\]\*sum\[k\])\}/\{2\*(j+sum\[j\]-k-sum\[k\])\}][sum_i_dp_j_-2_i-1-M_a_a_a-2_i-1-L_sum_j_2_j_sum_j_sum_j_sum_j_-_dp_j_-2_i-1-M_j_j_j-2_i-1-M_sum_k_2_k_sum_k_sum_k_sum_k_2_j_sum_j_-k-sum_k]

也就是最终转化成左边只有sum\[i\]的式子,这就相当于j，k两点的斜率，我们用单调队列维护一个斜率递增的j， k

对于top++, rear--操作：

当队列头的两个元素斜率小于sum【i】， 说明还能优化，所以top++，取更大的斜率

对于rear--是要维护一个下凸包。

[HYSBZ - 1010][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #define MAXN 500000+10
    #define LARGE 23333333
    using namespace std;
    typedef long long LL;
    int n, top, rear;
    LL dp[MAXN], M, sum[MAXN], S[MAXN];
    
    LL GetUp(int a, int b, int i)
    {
        return (dp[a]-2*(i-1-M)*a+a*a-2*(i-1-M)*sum[a]+2*a*sum[a]+sum[a]*sum[a])-
               (dp[b]-2*(i-1-M)*b+b*b-2*(i-1-M)*sum[b]+2*b*sum[b]+sum[b]*sum[b]);
    }
    
    LL GetDown(int a, int b)
    {
        return 2*(a+sum[a]-b-sum[b]);
    }
    
    int main()
    {
        scanf("%d%lld", &n, &M);
        LL tmp;
        sum[0]=dp[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%lld", &tmp);
            sum[i]=sum[i-1]+tmp;
        }
        top=rear=0;
        S[rear++]=0;
    
        for(int i=1; i<=n; i++)
        {
    
            while(top+1<rear && GetUp(S[top+1], S[top], i)<=GetDown(S[top+1], S[top])*sum[i]) top++;
            int j=S[top];
            dp[i]=dp[j]+(i-j-1+sum[i]-sum[j]-M)*(i-j-1+sum[i]-sum[j]-M);
            while(top+1<rear &&
                    GetUp(i, S[rear-1], i)*GetDown(S[rear-1], S[rear-2])<=GetUp(S[rear-1], S[rear-2], i)*GetDown(i, S[rear-1]))rear--;
            S[rear++]=i;
        }
        printf("%lld\n", dp[n]);
    
        return 0;
    }

[HDU 3507][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #define MAXN 500000+10
    #define LL long long
    #define LARGE 23333333
    using namespace std;
    
    int n, top, rear;
    LL dp[MAXN], M, sum[MAXN], S[MAXN];
    
    LL GetUp(int a, int b){
        return (dp[a]+sum[a]*sum[a])-(dp[b]+sum[b]*sum[b]);
    }
    
    LL GetDown(int a, int b){
        return 2*(sum[a]-sum[b]);
    }
    
    int main()
    {
       while(~scanf("%d%lld", &n, &M)){
            LL tmp;
            sum[0]=dp[0]=0;
            for(int i=1; i<=n; i++){
                scanf("%lld", &tmp);
                sum[i]=sum[i-1]+tmp;
            }
            top=rear=0;
            S[rear++]=0;
    
            for(int i=1; i<=n; i++){
    
                while(top+1<rear && GetUp(S[top+1], S[top])<=GetDown(S[top+1], S[top])*sum[i]) top++;
                int j=S[top];
                dp[i]=dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+M;
                while(top+1<rear &&
                      GetUp(i, S[rear-1])*GetDown(S[rear-1], S[rear-2])<=GetUp(S[rear-1], S[rear-2])*GetDown(i, S[rear-1]))rear--;
                S[rear++]=i;
            }
            printf("%lld\n", dp[n]);
       }
        return 0;
    }

[dp_i_min_dp_j_sum_i_-sum_j_i-j-1-L_2_ _i_j_0]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%3Dmin%28dp%5Bj%5D&plus;%28sum%5Bi%5D-sum%5Bj%5D&plus;i-j-1-L%29%5E2%29%20%28i%3Ej%3E%3D0%29
[dp_j_sum_i_-sum_j_i-j-1-L_2_dp_k_sum_i_-sum_k_i-j-1-L_2]: https://private.codecogs.com/gif.latex?dp%5Bj%5D&plus;%28sum%5Bi%5D-sum%5Bj%5D&plus;i-j-1-L%29%5E2%3E%3Ddp%5Bk%5D&plus;%28sum%5Bi%5D-sum%5Bk%5D&plus;i-j-1-L%29%5E2
[t_i-1-L]: https://private.codecogs.com/gif.latex?t%3D%28i-1-L%29
[sum_i_dp_j_-2_i-1-M_a_a_a-2_i-1-L_sum_j_2_j_sum_j_sum_j_sum_j_-_dp_j_-2_i-1-M_j_j_j-2_i-1-M_sum_k_2_k_sum_k_sum_k_sum_k_2_j_sum_j_-k-sum_k]: https://private.codecogs.com/gif.latex?sum%5Bi%5D%3E%3D%7B%28dp%5Bj%5D-2*%28i-1-M%29*a&plus;a*a-2*%28i-1-L%29*sum%5Bj%5D&plus;2*j*sum%5Bj%5D&plus;sum%5Bj%5D*sum%5Bj%5D%29-%28dp%5Bj%5D-2*%28i-1-M%29*j&plus;j*j-2*%28i-1-M%29*sum%5Bk%5D&plus;2*k*sum%5Bk%5D&plus;sum%5Bk%5D*sum%5Bk%5D%29%7D/%7B2*%28j&plus;sum%5Bj%5D-k-sum%5Bk%5D%29%7D
[HYSBZ - 1010]: https://www.lydsy.com/JudgeOnline/problem.php?id=1010
[HDU 3507]: http://acm.hdu.edu.cn/showproblem.php?pid=3507