文章目录
-
-
- 题目
- 题解
-
- 10pts: m = n ? 1 , y i = x i 1 m=n-1,y_i=x_i 1 m=n?1,yi=xi 1
- ex30pts: A = B = C = 0 A=B=C=0 A=B=C=0
- ex10pts: A = B = 0 A=B=0 A=B=0
- ?~100pts:
- 75pts: m ≤ 4000 m\leq 4000 m≤4000
- 100pts:
-
题目
原数据 数据加强版
题解
10pts: m = n − 1 , y i = x i + 1 m=n-1,y_i=x_i+1 m=n−1,yi=xi+1
限制很强，情况比较简单(是不标准的链)，数据很小，暴力维护各种信息，顺着随便做一遍应该就能过。
ex30pts: A = B = C = 0 A=B=C=0 A=B=C=0
这个时候花费只和最后到达 n n n节点的 q i q_i qi有关，直接做最短路维护最小的 q i q_i qi就可以了。
ex10pts: A = B = 0 A=B=0 A=B=0
当 A = B = 0 A=B=0 A=B=0时，除最后到达 n n n节点的 q i q_i qi的花费外，其余花费只与常数 C C C有关，而与具体的 p , q p,q p,q无关。用动态开点线段树维护 q q q时刻到达 i i i点时的花费，无脑取min即可。 事实上，这一档本身总共有40pts。
参考代码:
#include<bits/stdc++.h>
#define ll long long
#define uit unsigned int
using namespace std;
const int N=2e5+10,SLN=1e3+5;
const ll INF=1e18;
int n,m,root[N];ll A,B,C,ans=INF;
ll tr[N*15];int idx=0,ls[N*15],rs[N*15];
struct A{
int id,st,ed;ll p,q;
friend bool operator<(A x,A y){
return x.p<y.p;
}
}a[N];
void change(int &p,int l,int r,int pos,ll v){
if(!p) p=++idx,tr[p]=v;
else tr[p]=min(tr[p],v);
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) change(ls[p],l,mid,pos,v);
else change(rs[p],mid+1,r,pos,v);
}
ll Ask(int p,int l,int r,int L,int R){
if(!p) return INF;
if(L>R) return INF;
if(l>=L&&r<=R) return tr[p];
int mid=(l+r)>>1;ll temp=INF;
if(L<=mid) temp=min(temp,Ask(ls[p],l,mid,L,R));
if(R>mid) temp=min(temp,Ask(rs[p],mid+1,r,L,R));
return temp;
}
void solve(){
for(int i=1;i<=m;i++) scanf("%d%d%lld%lld",&a[i].st,&a[i].ed,&a[i].p,&a[i].q),a[i].id=i;
sort(a+1,a+m+1);
for(int i=1;i<=m;i++){
ll tmp=INF;
if(a[i].st==1) tmp=C;
else tmp=Ask(root[a[i].st],1,1000,1,a[i].p)+C,tmp=min(tmp,INF);
if(a[i].ed==n) ans=min(ans,tmp+a[i].q);
change(root[a[i].ed],1,1000,a[i].q,tmp);
}
printf("%lld\n",ans);
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d%lld%lld%lld",&n,&m,&A,&B,&C);
if(A==B&&A==0) solve();
return 0;
}
?~100pts:
暴搜。 每个节点做一个桶，存储从这个点出发的列车，记录 a n g e r anger anger和 t i m e time time暴力dfs。 可以预先对桶内按 p i p_i pi排序，这样如果枚举到 p i < t i m e p_i<time pi<time就可以直接break，而不用全部枚举一遍。 然后就A了。 原数据非常水，如果dfs实现的比较好就可以直接A掉。
75pts: m ≤ 4000 m\leq 4000 m≤4000
考虑DP。 设 f i f_i fi表示要经过 i i i条边，在经过这条边之前的最小花费，得到: f i = min { f j + A × ( p i − q j ) 2 + B × ( p i − q j ) + C } f_i=\min\{f_j+A\times(p_i-q_j)^2+B\times(p_i-q_j)+C\} fi=min{ fj+A×(pi−qj)2+B×(pi−qj)+C} 注意以下 j j j的限制即可。 理论复杂度 O ( m 2 ) O(m^2) O(m2)。 配合 A = B = 0 A=B=0 A=B=0的特殊点可拿到75pts。
100pts:
f i = min { f j + A × ( p i − q j ) 2 + B × ( p i − q j ) + C } f_i=\min\{f_j+A\times(p_i-q_j)^2+B\times(p_i-q_j)+C\} fi=min{ fj+A×(pi−qj)2+B×(pi−qj)+C}显然可以斜率优化。 得到: f j + A q j 2 − B q j = 2 A p i q j + f i − A p i 2 − B p i − C f_j+Aq_j^2-Bq_j=2Ap_iq_j+f_i-Ap_i^2-Bp_i-C fj+Aqj2−Bqj=2Apiqj+fi−Api2−Bpi−C 按照 p i p_i pi从小到大更新 d p i dp_i dpi,这样斜率 k k k单调不减。 考虑怎么维护 y j = x i y_j=x_i yj=xi和 q j ≤ p i q_j\leq p_i qj≤pi两个限制。 对于地点的限制，由于地点数较少，可以直接开 n n n和单调队列，无论是更新还是插入直接访问对应的单调队列即可。 对于时间的限制，根据套路，对于一个元素 i i i,可以把其先放在某个桶里，等到 i i i真正有作用(即 q j ≤ t i m e q_j\leq time qj≤time)时再将其加入单调队列。 然后斜率优化即可。
参考代码:
#include<bits/stdc++.h>
#define ll long long
#define uit unsigned int
#define df long double
using namespace std;
template<typename T> void read(T &x){
x=0;char c=getchar();bool flag=1;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') flag=0;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=flag?x:-x;
}
const int N=1e5+10,M=1e6+10;
const df INF=1e18;
int n,m,st[M],ed[M],h[M],t[M];ll A,B,C,T,p[M],q[M],X[M],Y[M],dp[M],ans=INF;
vector<int>bin[M],Q[N],ins[M];
df getk(int x,int y){
df delx=X[y]-X[x],dely=Y[y]-Y[x];
if(!delx){
if(dely>0) return INF;
else return -INF;
}
return dely/delx;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);read(A);read(B);read(C);
for(int i=1;i<=m;i++) read(st[i]),read(ed[i]),read(p[i]),read(q[i]),T=max(T,q[i]);
for(int i=1;i<=m;i++) bin[p[i]].push_back(i);
for(int i=1;i<=n;i++) h[i]=0,t[i]=-1;
for(int now=0;now<=T;now++){
for(int it:ins[now]){
int pp=ed[it];
while(h[pp]<t[pp]&&getk(Q[pp][t[pp]-1],Q[pp][t[pp]])>=getk(Q[pp][t[pp]-1],it)) t[pp]--;
++t[pp];
if(t[pp]>=Q[pp].size()) Q[pp].push_back(it);
else Q[pp][t[pp]]=it;
}
for(int it:bin[now]){
int pp=st[it];df K=2.0*A*p[it];
while(h[pp]<t[pp]&&getk(Q[pp][h[pp]],Q[pp][h[pp]+1])<K) h[pp]++;
int j;
if(h[pp]>t[pp]&&pp!=1) continue;
if(h[pp]>t[pp]&&pp==1) j=0;
else j=Q[pp][h[pp]];
dp[it]=dp[j]+A*(p[it]-q[j])*(p[it]-q[j])+B*(p[it]-q[j])+C;
X[it]=q[it];Y[it]=dp[it]+A*q[it]*q[it]-B*q[it];
ins[q[it]].push_back(it);
if(ed[it]==n) ans=min(ans,dp[it]+q[it]);
}
}
printf("%lld\n",ans);
return 0;
}