noi.ac NA534 【猫】

一眼暴力DP

再一眼决策单调性？

打个表以为是四边形不等式？？

最后发现是斜率优化？？？

于是成功写了个假斜率优化真四边形不等式拿了\(80\)

设\(f[i][j]\)表示有\(i\)个工作人员出发接回\(j\)只猫的最小等待时间和，转移点为\(u\)，则有：

\(f[i][j]+sum[j]=f[i-1][u]+j\cdot t[j]-u\cdot t[j]+sum[u]\)

于是随随便便写个斜率优化就过了

#include<bits/stdc++.h>

#define dqfront dq[dqfr]

#define dqsec dq[dqfr+1]

#define dqback dq[dqen]

#define dqbsec dq[dqen-1]

#define dqpb(u) dq[++dqen]=u

#define Lf long double

#define pii pair<int,int>

#define fi first

#define se second

#define mk make_pair

using namespace std;

const int N=1e5+5;

int n,m,p,d[N],h[N],t[N],sumd[N];

long long f[2][N],sumt[N];

int dq[N],dqfr,dqen;

int fr[1010][N];

long long cross(int u,int v,int w,int op){

	return 1LL*(v-u)*(f[op][w]+sumt[w]-f[op][v]-sumt[v])-1LL*(w-v)*(f[op][v]+sumt[v]-f[op][u]-sumt[u]);

}

long long cross(pii u,pii v){

	return 1LL*u.fi*v.se-1LL*u.se*v.fi;

}

int main(){

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

	if(p>=m){

		printf("0\n");return 0;

	}

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

		scanf("%d",&d[i]);

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

	}

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

		scanf("%d%d",&h[i],&t[i]);

		t[i]-=sumd[h[i]];

	}

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

	for(int i=m;i>0;i--){

		t[i]-=t[1];

	}

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

		sumt[i]=sumt[i-1]+t[i];

	}

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

		f[1][i]=1LL*i*t[i]-sumt[i];

	}

	for(int i=2;i<=p;i++){

		dqfr=0;dqen=0;

		for(int j=1;j<=m;j++){

			while(dqfr<dqen&&cross(mk(1,t[j]),mk(dqsec-dqfront,f[(i&1)^1][dqsec]+sumt[dqsec]-f[(i&1)^1][dqfront]-sumt[dqfront]))<=0){

				++dqfr;

			}

			fr[i][j]=dqfront;

			f[i&1][j]=f[(i&1)^1][dqfront]+1LL*(j-dqfront)*t[j]+sumt[dqfront]-sumt[j];

			while(dqfr<dqen&&cross(dqbsec,dqback,j,(i&1)^1)<=0){

				--dqen;

			}

			dqpb(j);

		}

	}

	printf("%lld\n",f[p&1][m]);

	return 0;

}

巴特西

noi.ac NA534 【猫】

最新文章

热门文章