贞鱼

众所周知，贞鱼是一种高智商水生动物。不过他们到了陆地上智商会减半。这不？他们遇到了大麻烦！

n只贞鱼到陆地上乘车，现在有k辆汽车可以租用。由于贞鱼们并不能在陆地上自由行走，一辆车只能载一段连续的贞鱼。

贞鱼们互相有着深深的怨念，每一对贞鱼之间有怨气值。第i只贞鱼与第j只贞鱼的怨气值记为Yij，且Yij=Yji，Yii=0。每辆车载重不限，但是每一对在同辆车中的贞鱼都会产生怨气值。

当然,超级贞鱼zzp长者希望怨气值的总和最小。不过他智商已经减半,想不出分配方案。他现在找到了你,请你帮助他分配贞鱼们,并输出最小怨气值之和ans。

1 ≤ n ≤4000 ，1 ≤ k ≤min(n , 800) , 0 ≤ Yij≤10

分析

显然每条鱼坐一辆车最优，代价为0。考虑二分一个权值，表示这辆车的价钱为C。如果C=0，就会选出n辆车，如果C=inf，就会只用一辆车。于是用这个权值逼近，直到选出刚好K辆车。此时选择的方案一定为最优解的一种方案。

DP方程：

\[F[i]=\min_{0\le j<i}\{F[j]+(s[i][i]+s[j][j]-s[i][j]*2)/2+C\}
\]

考虑题目中所给的那个两条鱼之间的代价，发现就是一个正方形数组里面在主对角线上选一个正方形求和。用二维前缀和维护即可。并且易证这个转移满足四边形不等式。

凸优化+决策单调性优化，时间复杂度\(O(n\log n\log w)\)

这个决策单调性优化有毒……换了一种维护版本才过的。并且二分后--l是什么操作……

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

using namespace std;

co int N=4001,INF=0x3f3f3f3f;

int n,K,s[N][N],g[N],f[N],C;

il int val(int j,int i){

	return j<i?f[j]+(s[i][i]+s[j][j]-s[i][j]*2)/2+C:INF;

}

struct Q{int x,l,r;}q[N];

int L,R;

void insert(int i){

	int w=-1;

	while(L<=R){

		if(val(i,q[R].l)<=val(q[R].x,q[R].l)) w=q[R--].l;

		else{

			if(val(q[R].x,q[R].r)>val(i,q[R].r)){

				int l=q[R].l,r=q[R].r;

				while(l<r){

					int mid=l+r>>1;

					if(val(i,mid)>val(q[R].x,mid)) l=mid+1;

					else r=mid;

				}

				q[R].r=l-1,w=l;

			}

			break;

		}

	}

	if(w!=-1) q[++R]=(Q){i,w,n};

}

void dp(){

	L=R=0,q[0]=(Q){0,1,n};

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

		while(L<=R&&q[L].r<i) ++L;

		f[i]=val(q[L].x,i),g[i]=g[q[L].x]+1;

		q[L].l=i+1;

		insert(i);

	}

}

int main(){

	read(n),read(K);

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

		for(int j=1;j<=n;++j) s[i][j]=read<int>()+s[i][j-1]+s[i-1][j]-s[i-1][j-1];

	int l=0,r=s[n][n];

	while(l<r){

		C=l+r>>1,dp();

		if(g[n]>K) l=C+1;

		else r=C;

	}

	C=l,dp();

	printf("%d\n",f[n]-g[n]*C);

	return 0;

}

巴特西

BZOJ5311,CF321E 贞鱼

贞鱼

分析

最新文章

热门文章