网络建站公司源码,简约网页,wordpress彩色标签云,photoshop中文版免费下载传送门
题意#xff1a;给定MMM个班车#xff0c;每个班车pip_ipi时刻从xix_ixi发车qiq_iqi到达yiy_iyi#xff0c;等车ttt时间花费代价At2BtCAt^2BtCAt2BtC,在ttt时刻到达花费ttt的代价#xff0c;求从111到NNN的最小花费。 1≤N≤100000,1≤M≤2000001 \leq N \…传送门
题意给定MMM个班车每个班车pip_ipi时刻从xix_ixi发车qiq_iqi到达yiy_iyi等车ttt时间花费代价At2BtCAt^2BtCAt2BtC,在ttt时刻到达花费ttt的代价求从111到NNN的最小花费。
1≤N≤100000,1≤M≤2000001 \leq N \leq 100000,1 \leq M \leq 2000001≤N≤100000,1≤M≤200000
显然是个dp
容易想到一个二维dp第一维记当前位置第二维记时间
由于数据范围很大所以需要优化掉一维
仔细想想为什么需要两维
因为位置是有后效性的需要用时间节点来标记。
而时间是一去不复返的是个天然的无后效性状态。
所以可以考虑按时间dp先假设没有位置限制。
此题对时间唯一的限制是不能冲突所以按照班车的时间段dp。
假设可以瞬间移动不计最终代价设坐上第iii辆班车的最小代价是fif_ifi
fiminqj≤pi{fjA(pi−qj)2B(pi−qj)C}f_i\min_{q_j \leq p_i}\{f_jA(p_i-q_j)^2B(p_i-q_j)C\}fiqj≤pimin{fjA(pi−qj)2B(pi−qj)C}
盲猜斜率优化
假设决策j,kj,kj,k有jkjkjk,kkk比jjj优
即
fkA(pi−qj)2B(pi−qj)C≤fjA(pi−qj)2B(pi−qj)Cf_kA(p_i-q_j)^2B(p_i-q_j)C\leq f_jA(p_i-q_j)^2B(p_i-q_j)CfkA(pi−qj)2B(pi−qj)C≤fjA(pi−qj)2B(pi−qj)C
fkA(pi−qj)2B(pi−qj)≤fjA(pi−qj)2B(pi−qj)f_kA(p_i-q_j)^2B(p_i-q_j)\leq f_jA(p_i-q_j)^2B(p_i-q_j)fkA(pi−qj)2B(pi−qj)≤fjA(pi−qj)2B(pi−qj)
fkApi2−2Apiqkqk2Bpi−Bqk≤fjApi2−2Apiqjqj2Bpi−Bqjf_kAp_i^2-2Ap_iq_kq_k^2Bp_i-Bq_k \leq f_jAp_i^2-2Ap_iq_jq_j^2Bp_i-Bq_jfkApi2−2Apiqkqk2Bpi−Bqk≤fjApi2−2Apiqjqj2Bpi−Bqj
fk−2Apiqkqk2−Bqk≤fj−2Apiqjqj2−Bqjf_k-2Ap_iq_kq_k^2-Bq_k \leq f_j-2Ap_iq_jq_j^2-Bq_jfk−2Apiqkqk2−Bqk≤fj−2Apiqjqj2−Bqj
2ApiB≥fkqk2−fj−qj2qk−qj2Ap_iB \geq\frac{f_kq_k^2-f_j-q_j^2}{q_k-q_j}2ApiB≥qk−qjfkqk2−fj−qj2
发现ppp和qqq分开了(其实不分开也能做的说)
所以可以把出发和到达拆开分别排序双指针维护
考虑位置限制
对于一个pip_ipi,只有yjxiy_jx_iyjxi的qjq_jqj会更新答案
所以可以用vector存NNN个凸壳
遇到出发在对应结点的凸壳上算出fff。因为脑袋抽了写了个二分。
遇到到达在对应结点用之前的fff更新凸壳
最后能到达NNN的算答案。
当时做的时候式子推反了然后二分的时候凸壳算反了就负负得正A了……
我可能是个傻子
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#include vector
#define MAXN 200005
using namespace std;
struct event{int idx,pos,tim;}st[MAXN],ed[MAXN];
inline bool cmp(const event a,const event b){return a.timb.tim;}
int n,m,A,B,C;
int f[MAXN];
inline int Y(const int i){return f[ed[i].idx]ed[i].tim*ed[i].tim;}
inline int calc(const int i,const int j)
{int dst[i].tim-ed[j].tim;return f[ed[j].idx]A*d*dB*dC;
}
vectorint v[MAXN];
int vis[MAXN];
int main()
{scanf(%d%d%d%d%d,n,m,A,B,C);for (int i1;im;i){int x,y,p,q;scanf(%d%d%d%d,x,y,p,q);st[i](event){i,x,p};ed[i](event){i,y,q};}memset(f,0x7f,sizeof(f));sort(st1,stm1,cmp);sort(ed1,edm1,cmp);int now0;for (int i1;im;i){while (nowmed[now1].timst[i].tim){now;if (vis[ed[now].idx]) continue;vectorint curv[ed[now].pos];while (cur.size()1(Y(now)-Y(cur[cur.size()-1]))*(ed[cur[cur.size()-1]].tim-ed[cur[cur.size()-2]].tim)((Y(cur[cur.size()-1])-Y(cur[cur.size()-2]))*(ed[now].tim-ed[cur[cur.size()-1]].tim))) cur.pop_back();cur.push_back(now);}if (st[i].pos1) f[st[i].idx]A*st[i].tim*st[i].timB*st[i].timC;else{vectorint curv[st[i].pos];if (cur.size()){int l0,rcur.size()-1,mid;while (lr){mid(lr)1;if ((2*A*st[i].timB)*(ed[cur[mid1]].tim-ed[cur[mid]].tim)Y(cur[mid1])-Y(cur[mid])) rmid;else lmid1;}f[st[i].idx]calc(i,cur[l]);}else vis[st[i].idx]true;}}int ansf[0];for (int i1;im;i) if (ed[i].posn) ansmin(ans,f[ed[i].idx]ed[i].tim);printf(%d\n,ans);return 0;
}
