【USACO 2021.1 P】T2. Minimum Cost Paths

题目链接

题目大意

一个 \(N \times M\) 的矩阵（ \(2 \le N \le 10^9\) ， \(2 \le M \le 2 \times 10^5\) ），走第 \(x\) 行距离为 \(x^2\) ， 走第 \(y\) 列距离为 \(c_y\) ， 问从 \(\left( 1,1 \right)\) 到 \(x , y\) 的最短距离，多组询问。

解法

一眼当然是 DP，

容易发现对于每一列，总有一个分界点，称其为拐点，使得 在分界点前，从前一列转移来；在分界点后，从前一行转移来。

考虑找出这个分界点，即可快速确定 DP 值。

由于拐点可能从若干列前转移过来，所以动态维护拐点的图形，离线询问，推推式子即可。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m,T,cnt;
ll f[N],c[N],ans[N];
struct node{int x,y;ll v;}a[N];
struct que{int x,y,id;}q[N];
ll sqr(ll x){return x*x;}
bool cmp(que a,que b){return a.y<b.y;}
int main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%d%d",&n,&m);
	fo(i,1,m)scanf("%lld",&c[i]);
	a[cnt=1]=(node){1,1,0};
	f[1]=1;
	scanf("%d",&T);
	fo(i,1,T){
		scanf("%d%d",&q[i].x,&q[i].y);
		q[i].id=i;
	}
	sort(q+1,q+T+1,cmp);
	int it=1;
	for(;it<=T && q[it].y==1;++it){
		ans[q[it].id]=c[1] * (q[it].x - 1);
	}
	a[cnt=1]=(node){1,1,0};
	fo(i,2,m){
		while(c[i] - c[a[cnt].y] < 2ll * a[cnt].x * (i - a[cnt].y) && cnt>1)--cnt;
		int x=a[cnt].x,y=a[cnt].y;
		if(c[i] - c[y] <= 2ll * x * (i - y))a[cnt].v+=sqr(x) * (i-y),a[cnt].y=i;
		else{
			int t=((c[i] - c[y] ) / (i - y) + 1) /2 -x;
			ll v=a[cnt].v + t * c[y] + sqr(x+t) * (i - y);
			a[++cnt]=(node){x + t ,i ,v};
			f[i]=cnt;
		}
		for(;it<=T && q[it].y==i;++it){
			x=q[it].x;
			if(x>=a[cnt].x){
				ans[q[it].id]=a[cnt].v + c[i] * (x - a[cnt].x);
				continue;
			}
			int l=1,r=cnt,mid;
			while(l<r-1){
				mid=l+r>>1;
				if(a[mid].x<=x)l=mid;
				else r=mid;
			}
			ans[q[it].id]=a[l].v + c[a[l].y] * (x - a[l].x) + sqr(x) * (i - a[l].y);
		}
	}
	fo(i,1,T)printf("%lld\n",ans[i]);
	
	return 0;
}