bzoj4518征途斜率优化

征途这是一道十分经典的斜率优化

我们可以从题目中的方差来想,也就很容易的到这个式子

\[ans=m^2*\frac{\sum_{i=1}^{m}{(x_i-{\overline{x}})^2}}{m}
\]

化简就会得到

\[ans=m*\sum_{i=1}^{m}{(x_i-{\overline{x}})^2}
\]

在化简得

\[ans={m*\sum_{i=1}^{m}{x_i}^2}+{\sum_{i=1}^{m}{x_i}}
\]

经过观察，我们可以很容易发现\(\sum_{i=1}^{m}{x_i}\)是定值，同时\(m*\sum_{i=1}^{m}{x_i}^2\)中的\(m\)也是定值，所以我们的目标就是让\(\sum_{i=1}^{m}{{x_i}^2}\)最小

我们令\(dp[i][j]=\min\{dp[i-1][j-k]+(sum[j]-sum[j-k])^2\}\)

其中我们令\(sum[i]=\sum_{k=1}^{i}{val_k}\)

其中\(val_k\)是第k段路的长度

由此我们就可得到一个开o2可以卡成80的代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cctype>

using namespace std;

long long n,m,dp[3001][3001],sum[3001];

    const int BufferSize=100*1000;

    char buffer[BufferSize],*head,*tail;

    bool not_EOF=true;

    inline char Getchar(){

        if(not_EOF and head==tail){

            int len=fread(buffer,1,BufferSize,stdin);

            not_EOF=len!=0;

            head=buffer,tail=head+len;

        }

        return not_EOF?*head++:-1;

    }

    inline long long rd(){

        long long x=0,s=1;

        char c=Getchar();

        for(;!isdigit(c) and not_EOF;c=Getchar()) if(c=='-') s=-1;

        for(; isdigit(c) and not_EOF;c=Getchar()) x=(x<<1)+(x<<3)+(c^48);

        return s*x;

    }

    inline void scan(char *str){

        char c=Getchar();

        for(; isspace(c) and not_EOF;c=Getchar());

        for(;!isspace(c) and not_EOF;c=Getchar()) *(str++)=c;

        *str=0;

}

int main(){

	memset(dp,0x7f,sizeof(dp));

	n=rd(),m=rd();

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

		long long x=rd();

		sum[i]=sum[i-1]+x;

	}

	dp[0][0]=-sum[n]*sum[n];

	for(int i=0;i<m;i++){

		for(int j=0;j<=n;j++){

			for(int k=0;k<=n-j;k++){

				dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+(sum[j+k]-sum[j])*(sum[j+k]-sum[j])*m);

			}

		}

	}

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

    return 0;

}

但是我们可以发现这个代码是\(O(nm)\)的，显然我是不可以接受的。其实我们可以很容易证明这个的决策单调性，于是我们就可以用斜率优化

我们令\(y<x<i\)

因为决策单调性，所以对于决策\(i\)时，k转移必定比j转移要优，我们就可以得到这么一个式子

\[dp[i-1][x]+(sum[j]-sum[x])^2<dp[i-1][y]+(sum[j]-sum[y])^2
\]

化简得

\[\frac{(dp[i-1][x]+sum[x]^2)-(dp[i-1][y]+sum[y]^2)}{sum[x]-sum[y]}<2*sum[j]
\]

这样我们就可以用斜率又花了

我们把\(p_1(dp[i-1][x]+sum[x]^2,sum[x])\)和\(p_2(dp[i-1][y]+sum[y]^2,sum[y])\)看做\(p_1,p_2\)两个点，刚刚那个式子也就是它们所连线的斜率表达式

我们也就可以得到这样的代码

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

long long n,m,dp[3001][3001],sum[3001];

int q[3001];

double getpoint(int i,int p){return (double)dp[i][p]+sum[i]*sum[i];}

double slope(int j,int k,int p){return (double)(getpoint(j,p)-getpoint(k,p))/(double)(sum[j]-sum[k]);}

int main(){

	scanf("%lld%lld",&n,&m);

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

		long long x;

		scanf("%lld",&x);

		sum[i]=sum[i-1]+x;

		dp[i][1]=sum[i]*sum[i];

	}

	for(int k=2;k<=m;k++){

		int head=1,tail=0;

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

            while(head<tail and slope(q[head],q[head+1],k-1)<2*sum[i])head++;

            int j=q[head];

            dp[i][k]=dp[j][k-1]+(sum[j]-sum[i])*(sum[j]-sum[i]);

            while(head<tail and slope(q[tail],q[tail-1],k-1)>slope(q[tail],i,k-1))tail--;

            q[++tail]=i;

        }

	}

    printf("%lld",m*dp[n][m]-sum[n]*sum[n]);

    return 0;

}

巴特西

bzoj4518征途斜率优化

征途这是一道十分经典的斜率优化

最新文章

热门文章

巴特西

bzoj4518征途 斜率优化

征途这是一道十分经典的斜率优化

最新文章

热门文章

bzoj4518征途斜率优化