笔记-Cats Transport

Cats Transport

令 \(D_i=\sum_{j=1}^id_i\)，\(T_i=t_i-D_{h_i}\)。

为 \(T_i\) 从小到大排序，令 \(s_i=\sum_{j=1}^iT_j\)。

设 \(f_{a,i}\) 表示第 \(a\) 个人带走猫子 \(i\) 的 \(1\sim i\) 号猫子最小等待时间之和。

设第 \(a-1\) 个人带走了第 \(j\) 个猫子，所以第 \(a\) 个人带走了第 \(j+1\sim i\) 个猫子。

所以递推式：

\[\begin{split}
f_{a,i}=&\min\{f_{a-1,j}+T_i(i-j)-(s_i-s_j)\}\\
f_{a,i}=&f_{a-1,j}+T_i(i-j)-(s_i-s_j)\\
f_{a,i}=&f_{a-1,j}+iT_i-jT_i-s_i+s_j\\
f_{a-1,j}+s_j=&T_i\cdot j+f_{a,i}+s_i-iT_i\\
\end{split}
\\
\begin{cases}
y=f_{a-1,j}+s_j\\
k=T_i\\
x=j\\
b=f_{a,i}+s_i-iT_i\\
\end{cases}
\\
\Large y=kx+b
\]

搞定。

Code

#include <bits/stdc++.h>

using namespace std;

//Start

#define re register

#define il inline

#define mk make_pair

#define pb push_back

#define db double

#define lng long long

#define fi first

#define se second

const int inf=0x3f3f3f3f;

const lng INF=0x3f3f3f3f3f3f3f3f;

//Data

const int N=100000,P=100;

int n,m,p;

lng d[N+7],t[N+7],s[N+7];

//DP

lng f[P+7][N+7];

pair<int,int> lor[P+7];

int q[P+7][N+7];

#define l(x) lor[x].fi

#define r(x) lor[x].se

il db X(re int a,re int j){

	return j;

}

il db Y(re int a,re int j){

	return f[a][j]+s[j];

}

il db slope(re int a,re int k,re int t){

	return (Y(a,k)-Y(a,t))/(X(a,k)-X(a,t));

}

il lng F(re int a,re int i,re int j){

	return f[a-1][j]+t[i]*(i-j)-(s[i]-s[j]);

}

il lng DP(){

	for(re int a=0;a<=p;a++){

		lor[a]=mk(1,0);

		q[a][++r(a)]=0;

	}

	for(re int a=1;a<=p;a++){

		for(re int i=1;i<=m;i++){

			// printf("(%d,%d)\n",a,i);

			while(l(a-1)<r(a-1)&&slope(a-1,q[a-1][l(a-1)],q[a-1][l(a-1)+1])<=t[i]) l(a-1)++;

			f[a][i]=F(a,i,q[a-1][l(a-1)]);

			while(l(a)<r(a)&&slope(a,q[a][r(a)-1],q[a][r(a)])>=slope(a,q[a][r(a)],i)) r(a)--;

			q[a][++r(a)]=i;

		}

	}

	return f[p][m];

}

//Main

int main(){

	scanf("%d%d%d",&n,&m,&p);

	if(p>=m) return puts("0"),0;

	for(re int i=2,x;i<=n;i++){

		scanf("%d",&x);

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

	}

	for(re int i=1,x,y;i<=m;i++){

		scanf("%d%d",&x,&y);

		t[i]=-d[x]+y;

	}

	sort(t+1,t+m+1);

	for(re int i=1;i<=m;i++) s[i]=s[i-1]+t[i];

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

	return 0;

}

\[\Huge\color{#ddd}{\texttt{---END---}}
\]

巴特西

笔记-Cats Transport<已写题解>

笔记-Cats Transport

Code

最新文章

热门文章