大师作文网【PASCAL】NOIP竞赛题 电话线 需要原代码,不必进行优化,只要给出最简单的转移方程的那个程序代码即可.
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/18 22:09:20
【PASCAL】NOIP竞赛题 电话线 需要原代码,不必进行优化,只要给出最简单的转移方程的那个程序代码即可.
架设电话线 (telewire)
最近,Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务,于是,她们要求FJ把那些老旧的电话线换成性能更好的新电话线.新的电话线架设在已有的N(2
架设电话线 (telewire)
最近,Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务,于是,她们要求FJ把那些老旧的电话线换成性能更好的新电话线.新的电话线架设在已有的N(2
第一遍看好像是用动态规划,即有状态转移方程
f[i]=min(f[i-1]+h[i-1,i]*c,f[i-1]+c*(h[i-1,i]-x)+x^2)
其中,有n根电线杆就有n个阶段,其中对于每根电线杆的状态应该为f[i],对于每个状态的决策即是不加高电线杆到加到与i-1根电线杆相同高度.有点晦涩,就是说你从不加高到加高到与前一根电线杆相同高度搜一遍（每根电线杆都要搜）,然后取最小值.
f[i]=min(f[i-1]+h[i-1,i]*c,f[i-1]+c*(h[i-1,i]-x)+x^2)
其中,有n根电线杆就有n个阶段,其中对于每根电线杆的状态应该为f[i],对于每个状态的决策即是不加高电线杆到加到与i-1根电线杆相同高度.有点晦涩,就是说你从不加高到加高到与前一根电线杆相同高度搜一遍（每根电线杆都要搜）,然后取最小值.