T2960 全民健身【思维Dp，预处理，差分优化】

Online Judge：YCJSOI

Label：Dp，思维题，预处理，滚动优化

题目描述

乐乐现在掌管一个大公司，办公楼共有n层。为了增加员工的身体素质，他决定在每层楼都建立一个活动室，活动室分乒乓球和排球两种。

已知每层楼喜欢乒乓球和排球的人数。

每个人的行走楼层数是他去自己喜欢的运动室的楼层数。

请你帮乐乐算算，每层楼应该建乒乓球还是排球，使得所有人行走楼层数总和最小。

输入

第一行一个整数n，表示楼层数量。

接下来n行，每行两个整数a和b，表示喜欢乒乓球和排球的人数。

输出

输出一个整数，表示所有人行走楼层总和的最小值。

样例

Input#1

Output#1

Input#2

Output#2

Hint

第一层建乒乓球室，第二层建排球室。行走楼层为5+4=9

对于30%的数据，n的范围\([2,20]\);;

对于80%的数据，n的范围\([2,500]\);

对于100%的数据，n的范围\([2,4000]\)，每层楼喜欢乒乓球和排球的人数范围\([1,10^5]\)。

题解

看数据范围应该是个Dp。

Ⅰ状态定义

一开始看题，不难定义出这样一个状态\(dp[co=0/1][i][j]\)，意义是，已经决策完了前i层建什么，且\([j+1,i]\)这些层建的都是\(co\)，也就是\(j\)这一层建的是\(co\)^\(1\)，此时的最小代价。

但有一个问题，\([j+1,i]\)这些层喜欢\(co\)^\(1\)的人，他们一定是去\(j\)这层吗?不一定，可能还可以去i后面的某点，所以我们无法在当前状态中得知那个最小代价，我们能求得的只有\([1,j]\)这些层所有人的代价+\([j+1,i]\)这些层中喜欢\(co\)的人的代价(为0)。

说人话就是，如果我在\([j+1,i]\)这些层都建乒乓球室，1.那么\([j+1,i]\)这些层中打乒乓球的人都不用移动在本层打就好了(代价为0)，2.在\([1,j]\)这些层的人不论他喜欢乒乓球还是排球都可以在i之前做出决策，3.在\([j+1,i]\)这些层中喜欢排球的人无法在当前层状态中做出决策，因为他们可以选择去第\(j\)层打排球，但如果楼上还有更近的排球管呢？我们在当前状态中无法预知。

所以改一下意义，它表示的是[1,j]这些层所有人的代价+[j+1,i]这些层中喜欢co的人的代价。

Ⅱ转移

初始化如下

memset(dp,-1,sizeof(dp));//相当于赋一个极大值

dp[0][1][0]=dp[1][1][0]=0;

转移采用填表方式，更新最小值。

for(i=1;i<n;++i)for(j=0;j<i;++j)for(x=0;x<=1;++x)if(~dp[x][i][j]){

//枚举当前层i，[j+1,i]都建x

		for(y=0;y<=1;++y){//枚举第i+1层建什么

			if(x==y)Do(dp[y][i+1][j],dp[x][i][j]);//如果建的和i相同

			else{

				ll val=calc(y,j+1,i);

				if(~val)Do(dp[y][i+1][i],dp[x][i][j]+val);

			}

		}

}

主要看到\(x!=y\)时的情况，我们此时在中间\([j+1,i]\)建了\(x\)，在两端\(j,i+1\)建了\(y(!x)\)，那个\(calc(co,l,r)\)函数，求的就是\([l,r]\)这些层中喜欢\(co\)的人，分别去到\(l-1，r+1\)的最小代价。

很明显以中点为边界，左半边的去\(l-1\)，右半边的去\(r+1\)最优吧。

最low的求法应该就是下面这种\(O(N)\)的：

虽然非常暴力，但一定要注意下面几处特判。

inline ll calc(int co,int l,int r){

    ll sum=0;

    register int i,mid=(l+r)>>1;

    if(l==1&&r==n)return 1e9;//左右都不能去

    if(l==1){//左边不能去

        for(i=l;i<=r;++i)sum+=(r-i+1)*a[co][i];

        return sum;

    }

    if(r==n){//右边不能去

        for(i=l;i<=r;i++)sum+=(i-l+1)*a[co][i];

        return sum;

    }

    for(i=l;i<=mid;++i)sum+=(i-l+1)*a[co][i];//左半边的去l-1层

    for(i=mid+1;i<=r;++i)sum+=(r-i+1)*a[co][i];//右半边的去r+1层

    return sum;

}

最后的统计答案如下。别忘了还要加上最后一段代价。

for(x=0;x<=1;++x)for(j=1;j<n;++j){

	if(~dp[x][n][j])Do(ans,dp[x][n][j]+calc(x^1,j+1,n));

}

这样，大致的算法流程就结束了。但是也许在上面代码中你就发现了，空间、时间对于100%数据都承受不了（时间复杂度为\(O(4\cdot N^3)\)），只能过掉80%数据。

Ⅲ优化·空间

空间的话，主要是原来的\(dp[2][N][N]\)数组内存好像有点玄，所以求稳优化一波。由于每个\(i\)只用到上一层状态，所以直接滚动就好了，变成dp[2][2][N]。

Ⅲ优化·时间

时间呢，感觉那个calc(co,l,r)函数非常可优化的样子。在草稿纸上列了一下，发现可以利用差分思想，\(O(N)\)预处理前缀/后缀，然后\(O(1)\)计算出结果。

举个例子：对于求\([l,r]\)到它\(l-1\)的代价

比如\(l=4,r=7\)的情况：

列式为\(cost=a[4]*1+a[5]*2+a[6]*3+a[7]*4\)。

我们预处理一个前缀值：isum[i]=\((a[1]*1+a[2]*2+a[3]*3+..a[i]*i)\)；

然后再处理一个普通的前缀和：s[i]=(a[1]+a[2]+a[3]+..a[i])；

那么上式\(cost=isum[7]-(s[7]-s[3])*3\)。

推广一下可以得到：

inline ll getL(int co,int l,int r){//求[l,r]这些层中喜欢co的人跑到第l-1层的代价

	ll sum=0;

	sum=(isum[0][co][r]-isum[0][co][l-1])-1ll*(l-1)*(s[co][r]-s[co][l-1]);

	return sum;

}

类似的，去右端的情况，预处理一个后缀值即可，下面不再赘述。

综上，时间复杂度为\(O(N^2)\)。

完整代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=4002;

ll ans=-1;

int a[2][N],n;

inline int read(){

    int x=0;char c=getchar();

    while(c<'0'||c>'9')c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();

    return x;

}

inline void Do(ll &x,ll y){if(x==-1||x>y)x=y;}

ll s[2][N],isum[2][2][N];//isum:sum of i*val

void pre(){

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

		for(int x=0;x<=1;x++){

			s[x][i]=s[x][i-1]+a[x][i];

			isum[0][x][i]=isum[0][x][i-1]+1ll*a[x][i]*i;

		}

	}

	for(int i=n;i>=1;i--){

		for(int x=0;x<=1;x++){

			isum[1][x][i]=isum[1][x][i+1]+1ll*a[x][i]*(n-i+1);

		}

	}

}

inline ll getL(int co,int l,int r){

	ll sum=0;

	sum=(isum[0][co][r]-isum[0][co][l-1])-1ll*(l-1)*(s[co][r]-s[co][l-1]);

	return sum;

}

inline ll getR(int co,int l,int r){

	ll sum=0;int id=n-r;

	sum=(isum[1][co][l]-isum[1][co][r+1])-1ll*id*(s[co][r]-s[co][l-1]);

	return sum;

}

inline ll calc(int co,int l,int r){//[l,r]可以去l-1,r+1

    register int i,mid=(l+r)>>1;

    if(l==1&&r==n)return -1;

    if(l==1)return getR(co,l,r);

    if(r==n)return getL(co,l,r);

	return getL(co,l,mid)+getR(co,mid+1,r);

}

ll dp[2][2][N];

namespace p100{

	void solve(){

		pre();

		memset(dp,-1,sizeof(dp));

		register int i,j,x,y,g=0;

		memset(dp[g],-1,sizeof(dp[g]));

		dp[0][g][0]=dp[1][g][0]=0;

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

			g^=1;

			memset(dp[0][g],-1,sizeof(dp[0][g]));

			memset(dp[1][g],-1,sizeof(dp[1][g]));

			for(j=0;j<i;++j)for(x=0;x<=1;++x)if(~dp[x][g^1][j]){

				for(y=0;y<=1;++y){

					if(x==y)Do(dp[y][g][j],dp[x][g^1][j]);

					else{

						ll val=calc(y,j+1,i);

						if(~val)Do(dp[y][g][i],dp[x][g^1][j]+val);

					}

				}

			}

		}

		for(x=0;x<=1;++x)for(j=1;j<n;++j){

			if(~dp[x][g][j])Do(ans,dp[x][g][j]+calc(x^1,j+1,n));

		}

		printf("%lld\n",ans);

	}

}

int main(){

	n=read();

	for(int i=1;i<=n;++i)a[0][i]=read(),a[1][i]=read();

	p100::solve();

}

upd:由于上面代码比较丑，所以在博客文件里还放了几位学长的解析。

巴特西

T2960 全民健身【思维Dp，预处理，差分优化】

题目描述

输入

输出

样例

题解

Ⅰ状态定义

Ⅱ转移

Ⅲ优化·空间

Ⅲ优化·时间

最新文章

热门文章