USACO21JAN Minimum Cost Paths P

发布时间:2023年12月22日

洛谷P7294 [USACO21JAN] Minimum Cost Paths P

题目大意

有一个 n × m n\times m n×m的方阵,记帝 x x x行第 y y y列的格子为 ( x , y ) (x,y) (x,y),对于每一列有一个代价 c y c_y cy?

棋子从 ( 1 , 1 ) (1,1) (1,1)出发,当处于 ( x , y ) (x,y) (x,y)的时候,有以下两种选择:

  • 如果 y < m y<m y<m,即棋子不在最后一列,则棋子可以以 x 2 x^2 x2的代价移动到下一列
  • 如果 x < n x<n x<n,即棋子不在最后一行,则棋子可以以 c y c_y cy?的代价移动到下一行

q q q次询问,每次给定目标位置 ( x i , y i ) (x_i,y_i) (xi?,yi?),求棋子从 ( 1 , 1 ) (1,1) (1,1)移动到 ( x i , y i ) (x_i,y_i) (xi?,yi?)的最小代价。

对于 25 % 25\% 25%的数据,满足 c 2 > c 3 > ? > c m c_2>c_3>\cdots >c_m c2?>c3?>?>cm?

2 ≤ n ≤ 1 0 9 , 2 ≤ m ≤ 2 × 1 0 5 , 1 ≤ q ≤ 2 × 1 0 5 , 1 ≤ c y ≤ 1 0 9 2\leq n\leq 10^9,2\leq m\leq 2\times 10^5,1\leq q\leq 2\times 10^5,1\leq c_y\leq 10^9 2n109,2m2×105,1q2×105,1cy?109


题解

有一个部分分是 c 2 > c 3 > ? > c m c_2>c_3>\cdots >c_m c2?>c3?>?>cm?,那么最优路径一定是先从 ( 1 , 1 ) (1,1) (1,1)向下走到 ( t , 1 ) (t,1) (t,1),然后向右走到 ( t , y ) (t,y) (t,y),最后向下走到 ( x , y ) (x,y) (x,y)。为什么呢?因为在这种情况下,最优路径中只能是在第一列或第 y y y列向下走,否则将向下走的部分平移到第 y y y行一定更优。

我们来计算一下这条路径的代价。这条路径是 ( 1 , 1 ) → ( t , 1 ) → ( t , y ) → ( x , y ) (1,1)\to (t,1)\to (t,y)\to (x,y) (1,1)(t,1)(t,y)(x,y),那么代价为 ( t ? 1 ) × c 1 + ( y ? 1 ) × t 2 + ( x ? t ) × c y (t-1)\times c_1+(y-1)\times t^2+(x-t)\times c_y (t?1)×c1?+(y?1)×t2+(x?t)×cy?

我们发现,这是一个关于 t t t的二次函数 f ( t ) = ( y ? 1 ) × t 2 + ( c 1 ? c y ) × t + x × c y ? c 1 f(t)=(y-1)\times t^2+(c_1-c_y)\times t+x\times c_y-c_1 f(t)=(y?1)×t2+(c1??cy?)×t+x×cy??c1?,当 t t t c y ? c 1 2 ( y ? 1 ) \dfrac{c_y-c_1}{2(y-1)} 2(y?1)cy??c1?? f ( t ) f(t) f(t)取得最小值。而因为要求的 t t t是整数,所以当代价最小时 t t t的值为与 c y ? c 1 2 ( y ? 1 ) \dfrac{c_y-c_1}{2(y-1)} 2(y?1)cy??c1??相差最小的整数的值,也就是 c y ? c 1 2 ( y ? 1 ) \dfrac{c_y-c_1}{2(y-1)} 2(y?1)cy??c1??四舍五入后的值。

进一步地,我们发现,对于任意两列 y 1 , y 2 y_1,y_2 y1?,y2?,设 x 0 x_0 x0? c y 2 ? c y 1 2 ( y 2 ? y 1 ) \dfrac{c_{y_2}-c_{y_1}}{2(y_2-y_1)} 2(y2??y1?)cy2???cy1???四舍五入后的值,我们在第 x 0 x_0 x0?行转移是最优的,记 P ( y 1 , y 2 ) = x 0 P(y_1,y_2)=x_0 P(y1?,y2?)=x0?

我们先忽略 x x x的限制,对于每一组询问中,从 1 1 1 y y y的最小代价的路径一定经过若干个 y 1 , y 2 , … , y k y_1,y_2,\dots,y_k y1?,y2?,,yk?,其中从 y i → y i + 1 y_i\to y_{i+1} yi?yi+1?都选择 P ( y i , y i + 1 ) P(y_i,y_{i+1}) P(yi?,yi+1?)对应的路径。

那么,我们可以对 y y y离线,用单调栈维护当前转移路径上所有的 y i y_i yi?。因为 c y 2 ? c y 1 2 ( y 2 ? y 1 ) \dfrac{c_{y_2}-c_{y_1}}{2(y_2-y_1)} 2(y2??y1?)cy2???cy1???可以看做斜率 × 1 2 \times \dfrac 12 ×21?,而随着 y y y增加,转折的部分 P ( y i , y i + 1 ) P(y_i,y_{i+1}) P(yi?,yi+1?)也是递增的,所以单调栈中需要满足 y i y_i yi?斜率递增。可以用调整法来证明这一贪心策略的正确性。

注意因为 x 0 x_0 x0? [ 1 , n ] [1,n] [1,n]的范围内,所以要将 P ( y i , t i + 1 ) P(y_i,t_{i+1}) P(yi?,ti+1?)调整到 [ 1 , n ] [1,n] [1,n]上,对 1 1 1 max ? \max max再对 n n n max ? \max max即可。

再来考虑 x x x的限制。对于每次询问中 x x x的限制,我们在单调栈中二分找到最后一段 斜率 × 1 2 ≤ x \times \dfrac 12\leq x ×21?x 的部分,那么 ( x c , y c ) (x_c,y_c) (xc?,yc?) ( x , y ) (x,y) (x,y)也是先向下再向右最后向下,设末尾为 ( x c , y c ) (x_c,y_c) (xc?,yc?),则再按上面的方式用二次函数求 ( x c , y c ) (x_c,y_c) (xc?,yc?) ( x , y ) (x,y) (x,y)的最小代价即可。

时间复杂度为 O ( q log ? m ) O(q\log m) O(qlogm)

code

#include<bits/stdc++.h>
#define ll __int128
using namespace std;
const int N=200000;
int n,m,Q,tp=1,s[N+5];
long long c[N+5],sum[N+5],ans[N+5];
struct node{
	long long x,y;
	int id;
};
vector<node>q[N+5];
long long slope(int x,int y){
	int re=round((c[y]-c[x])*1.0/(2*(y-x)));
	re=max(re,1);re=min(re,n);
	return re;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%lld",&c[i]);
	}
	scanf("%d",&Q);
	for(int i=1,x,y;i<=Q;i++){
		scanf("%d%d",&x,&y);
		q[y].push_back((node){x,y,i});
	}
	for(node v:q[1]){
		ans[v.id]=c[1]*(v.x-1);
	}
	s[tp]=1;sum[tp]=0;
	for(int i=2;i<=m;i++){
		while(tp>1&&slope(s[tp-1],s[tp])>=slope(s[tp],i)) --tp;
		long long now=slope(s[tp],i),lst;
		if(tp==1) lst=1;
		else lst=slope(s[tp-1],s[tp]);
		sum[tp+1]=sum[tp]+(now-lst)*c[s[tp]]+(i-s[tp])*now*now;
		s[++tp]=i;
		for(node v:q[i]){
			int l=2,r=tp,mid,re;
			while(l<=r){
				mid=l+r>>1;
				if(slope(s[mid-1],s[mid])<=v.x) l=mid+1;
				else r=mid-1;
			}
			re=l-1;
			long long tmp;
			if(re==1) tmp=1;
			else tmp=slope(s[re-1],s[re]);
			ans[v.id]=sum[re]+(v.x-tmp)*c[s[re]]+(i-s[re])*v.x*v.x;
		}
	}
	for(int i=1;i<=Q;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}
文章来源:https://blog.csdn.net/tanjunming2020/article/details/135154759
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。