律师网站设计,山西太原百度公司,南京网络推广,外包公司离职一定要一个月吗大家来到这一堂课#xff0c;就说明大家已经学过函数了
直线方程#xff1a;ykxb 大家可以算一算。
其实#xff0c;在数学上#xff0c;这玩意要分类讨论 那么#xff0c;这唯一的交点就是我们要背出来的 直线最值 这像一个分段函数 其实#xff0c;只有部分直线能提供…大家来到这一堂课就说明大家已经学过函数了
直线方程ykxb 大家可以算一算。
其实在数学上这玩意要分类讨论 那么这唯一的交点就是我们要背出来的 直线最值 这像一个分段函数 其实只有部分直线能提供最小值另外的就可以省略
当然最大值也一样。
看一下太戈编程第2627题
题目 在平面直角坐标系里横坐标为x纵坐标为y。有n条直线第i条直线的形式为yb[i]k[i]*x。其中整数b[i]为截距整数k[i]为斜率。已知k[i]随着i的增加而减小。另外有m个从小到大排布的横坐标第i个为x[i]。请求出在每个横坐标位置上各个直线的纵坐标最小值是多少纯数学
暴力
struct Line{ll b,k;} lines[N];
int main(){ll n,m;cinnm;for(ll i1;in;i) cinlines[i].b;for(ll i1;in;i) cinlines[i].k;for(ll i1;im;i) cinx[i];for(ll i1;im;i){ans[i]INF;for(ll j1;jn;j){ans[i]min(ans[i],lines[j].blines[j].k*x[i]);}}for(int i1;im;i) coutans[i] ;return 0;
}
时间复杂度不太行
优化
根据前面的分析 但是这好像只能做到常数级别的优化 注意斜率递减
2号和0号的节点在2号和1号节点左侧那么说明1号线是废线可以省略。
做之前要做准备工作
struct Line{ll b,k;} lines[N];
ld X(ll u,ll v){return -(ld)(lines[u].b-lines[v].b)/(lines[u].k-lines[v].k);
}
然后我们维护一个队列里面是可能参与最小值的直线编号
ll l1,r1;
for(ll i1;in;i){while(r-l2X(i,q[r-1])X(q[r-1],q[r-2])) r--;q[r]i;
}
筛完了剩下一个上凸轮廓。那么一条直线只会提供一部分最小之后的我们称之为“过气的直线”
假设现在有两条直线l,l1程序运行到x[i]。当x[i]在交点右侧时l1提供最小当x[i]在交点左侧时l1不能提供最小。
for(ll i1;im;i){while(r-l2X(q[l],q[l1])x[i]) l;int jq[l];ans[i]lines[j].blines[j].k*x[i];
}
书籍叠放1
题目
你有n本书编号1到n需要分几堆叠放在桌面上。每本书的正面都是一个长方形共四条边左右两侧边长对应长方形的长度上下两侧边长对应长方形的宽度。第i本书的长度为h[i]宽度为w[i]。你可以选择任意几本书分出任意的堆数。但是叠放的时候要注意每本书两两之间都保持上下左右四条边平行不能旋转。每组叠放好的书都会在桌面上占据一定的面积。例如我们将3本书叠放在一堆里第一本长度为1宽度为4第二本长度为2宽度为3第三本长度为3宽度为2这三本占据的面积为长度为3宽度为4的长方形面积也就是3*412。 目前已知你的书籍满足一种特殊顺序你发现随着编号i增加书的长度h[i]增加宽度w[i]减少。请问经过合理叠放后总体占据的面积最小是多少
这是一道dp题可以用朴素
朴素
cinn;
for(ll i1;in;i) cinbk[i].hbk[i].w;
for(ll i1;in;i){f[i]bk[1].w*bk[i]*h;for(ll j1;ji;j)f[i]min(f[i],f[j]bk[j1].w*bk[i].h);
}
优化 这个看起来像直线最值吗 解释完毕
索道选址II
题目描述
lester的老家有一个著名的旅游景点大牛山。据说爬完就能成为C大牛所以游客不断。从山脚到山顶共有n个景点排成一条直线。山顶为景点n并且只有这一条登山路线orz。由于山太高当地政府决定架设若干条索道站点。索道站点山上某个景点并且到山顶景点n是必须有索道站点的。在景点i修建索道站点的花费为Ai。对于没有索道直达的景点游客会乘坐高于该景点且最近的一个索道站点然后从该站点向下走到目的地。步行游客会产生一定的不满意度值等于索道站点与目的地编号之差。你可以认为想去每个景点的游客人数是相同的例如索道站点在景点36则去景点4需要先到景点6然后向下走到景点4不满意度为6-42。lester既不想花太多钱又不愿意积累太多的不满意度。注意游客出发的位置可以理解为在0号而不是1号。他希望求一种折衷方案使得花费与不满意度总和最小。
f[i]表示用前i个选址覆盖前i个景点最小代价且上一段为j。则不满意度为
也就是j1加到i-1。 最后我们以-j为斜率f[j]1/2*(j1)*j为截距画直线
