【学习笔记】[USACO21JAN] Minimum Cost Paths P

本文主要是介绍【学习笔记】[USACO21JAN] Minimum Cost Paths P，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

京都观光的加强版😅

考虑怎么算贡献。首先还是求出 ${c_i\}$ 对应的凸包，然后对于每个 $c_i$ ，我们可以二分求出其被插入到了第 $j$ 行的后面，记这一行为 $p_i$ ， $c_i$ 对应第 $y_i$ 列， $p_{m}=x$ ，那么答案是:

$\sum_{i=1}^{m-1}c_i(p_{i+1}-p_i)+\sum_{i=2}^{m-1}p_i^2(y_{i}-y_{i-1})$

这样，我们将询问离线下来，处理出单调栈中前缀和对应的答案，二分出这段前缀即可。

复杂度 $O(q\log m)$ 。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
int n,m,Q;
int cnt,s[N];
ll c[N],res[N],sm[N],p[N];
vector<pair<int,int>>q[N];
ll calc(pair<ll,ll>x,pair<ll,ll>y){return x.fi*y.se-x.se*y.fi;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++)cin>>c[i];cin>>Q;for(int i=1;i<=Q;i++){int x,y;cin>>x>>y;q[y].pb({x,i});}p[1]=1;s[0]=1;for(int i=1;i<=m;i++){while(cnt>1&&calc({i-s[cnt],c[i]-c[s[cnt]]},{s[cnt]-s[cnt-1],c[s[cnt]]-c[s[cnt-1]]})>0)cnt--;s[++cnt]=i;if(cnt>1){p[cnt]=(1.0*(c[s[cnt]]-c[s[cnt-1]])/(s[cnt]-s[cnt-1])+1)/2;p[cnt]=max(p[cnt],1ll);sm[cnt]=sm[cnt-1]+c[s[cnt-1]]*(p[cnt]-p[cnt-1])+p[cnt-1]*p[cnt-1]*(s[cnt-1]-s[cnt-2]);}for(auto e:q[i]){ll x=e.fi;int id=e.se;if(cnt==1)res[id]=(x-1)*c[1];else{int l=1,r=cnt,tmp=0;while(l<=r){int mid=l+r>>1;if(p[mid]<=x)tmp=mid,l=mid+1;else r=mid-1;}res[id]=sm[tmp]+c[s[tmp]]*(x-p[tmp])+p[tmp]*p[tmp]*(s[tmp]-s[tmp-1])+(i-s[tmp])*x*x;}}}for(int i=1;i<=Q;i++)cout<<res[i]<<"\n";
}