题面

传送门

思路

把$vm^2$展开化一下式子，可以得到这样的等价公式：

$vm^{2=m\sum_{i=1}}m a_i^2-\sum_{i=1}m a_i$

那么我们要最小化的就是$\sum_{i=1}^m a_i^2$这个东西

设$dp[i][j]$表示前i段路程走了j天

转移显然：$dp[i][j]=min(dp[k][j-1]+dis(k,i)^2)(k=1...i-1)$

这就是个模板的斜率优化dp了

总复杂度$O(nm)$

Code：

写代码的时候需要注意一点：当前这一层的状态，要等到这一层（同一个i）都推完了，再一起入队，不然容易互相之间造成影响，导致WA

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

inline int read(){

    int re=0,flag=1;char ch=getchar();

    while(ch>'9'||ch<'0'){

        if(ch=='-') flag=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

    return re*flag;

}

int n,m,a[3010],q[3010][3010],l[3010]={0},r[3010]={0},maxq=3000;

ll dp[3010][3010],pre[3010];

ll up(int x,int y,int k){

    return dp[x][k]-dp[y][k]+pre[x]*pre[x]-pre[y]*pre[y];

}

ll down(int x,int y,int k){

    return 2ll*(pre[x]-pre[y]);

}

int main(){

    n=read();m=read();int i,j;

    for(i=1;i<=n;i++) a[i]=read(),pre[i]=pre[i-1]+a[i];

    q[0][r[0]++]=0;

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

        for(j=max(1,m+i-n)-1;j<i;j++){//先取得状态

            while(l[j]<r[j]-1&&up(q[j][l[j]+1],q[j][l[j]],j)<down(q[j][l[j]+1],q[j][l[j]],j)*(ll)pre[i]) q[j][l[j]++]=0;

            dp[i][j+1]=dp[q[j][l[j]]][j]+(pre[i]-pre[q[j][l[j]]])*(pre[i]-pre[q[j][l[j]]]);

        }

        for(j=max(1,m+i-n);j<=i;j++){//分开入队

            while(l[j]<r[j]-1&&up(i,q[j][r[j]-1],j)*down(q[j][r[j]-1],q[j][r[j]-2],j)<=down(i,q[j][r[j]-1],j)*up(q[j][r[j]-1],q[j][r[j]-2],j)) q[j][--r[j]]=0;

            q[j][r[j]++]=i;

        }

    }

    ll ans=0,mm=m;

    ans=mm*dp[n][m]-pre[n]*pre[n];

    cout<<ans;

}

巴特西

[SDOI2015][bzoj4518] 征途 [斜率优化dp]

题面

思路

Code：

最新文章

热门文章