admin管理员组文章数量:1657387
XYLX 10.19 天堂(HEAVEN)
题目描述
每一个要上天堂的人都要经历一番考验,当然包括小X,小X开始了他进入天堂的奇异之旅。地狱有18层,天堂竟然和地狱一样,也有很多很多层,天堂共有N层。从下到上依次是第1,2,3,…,N层,天堂的每一层都是一个延伸无限远的地板,在地板上人可以任意走动,层与层之间是平行关系,每一层的地板都是由人不能穿过的物质构成,幸好每一层地板上有且仅有1个人可以通过的洞口。
我们可以把小X和洞口,还有下面提到的气球店都看成点,坐标是二维的。小X开始在第1层的(0,0).
小X的重量为M,第i层与第i+1层之间的特殊气体能浮起的重量为Wi ,每一层的地面上散落了若干个气球店,多个气球店可以在同一点,每个气球可以浮起的重量是1,去一个气球店一次只能领取一个气球,不能连续在一个气球店领取气球,当然你可以在两个气球店之间来回跑,每个气球店供应的气球都是无限多的。第i层的气球只能在第i层进入第i+1层时使用,当小X在第i层,只有站到了第i+1层洞口的位置(在其它位置不会浮起),并且自身的重量小于等于气球和特殊气体浮起重量的总和,才可以进入第i+1层。小X想知道他要到达第N层走过的长度最少是多少?题目保证有解。
输入输出
输入文件
第1行: 三个正整数N,M,Q(Q表示气球店)
第2行: 共2*(N-1)个整数,每两个数描述1个洞口坐标,第i对xi,yi表示第i+1层的洞口位置(xi,yi)。
第3行: 共N-1个整数,第i个数为Wi。
往后Q行,每行三个整数x,y,z , 表示第Z层有一个气球店,坐标为(x,y)
输出文件
1个实数L,保留两位小数,表示小X最少要走的长度。
样例
样例输入
3 10 4
0 0 1 2
9 0
0 1 1
2 3 1
0 1 2
1 1 2
样例输出
13.00
注释
【样例解释】
在第一层从(0,0)出发到(0,1)取得1个气球并返回(0,0)即可到达第二层。长度:2.00
在第二层,从(0,0)到(0,1)领取气球,再到(1,1)领取气球,两个点来回跑,第5次到达(1,1)时恰好气球数达到10,走到(1,2)即可到达第3层终点。长度:11.00
总长度:13.00
【数据范围】
2<=N<=100
每层的气球店数目不超过50。
0<=M<=100, 0<=Wi<=100
坐标-3000<=x,y<=3000
分析
从网上看题解后自己的总结
首先要到最高层,每层都是互不影响的,所以分层动归,当每层都是最小的时候肯定所有也是最小,因此我们对该题分层动归,当特殊气球即可满足需求时代价就为从一点到另一点的距离;
方程
f[i,j]:=min(f[i,j],f[i-1,p]+从p气球店到j气球店的距离)(p<>j,p∈该层所有气球店)
f[1,j]:=(从起点到j气球店的距离)
代码如下
program heaven;
type rec=record
x,y:longint;
end;
var i,j,k,p,n,m,q,w,x,y,z:longint;
ans,minn:double;
sum:array[1..100] of integer;
balloon:array[1..100,1..50] of rec;
need:array[1..100] of longint;
elevator:array[1..100] of rec;
f:array[0..100,1..100] of double;
function min(a,b:double):double;
begin
if a<b then exit(a);
exit(b);
end;
begin
readln(n,m,q);
for i:=1 to n-1 do
begin
read(elevator[i].x,elevator[i].y);
end;
for i:=1 to n-1 do
begin
read(w);
need[i]:=m-w;
end;
for i:=1 to q do
begin
readln(x,y,z);
inc(sum[z]);
balloon[z,sum[z]].x:=x;
balloon[z,sum[z]].y:=y;
end;
x:=0;
y:=0;
for i:=1 to n-1 do
begin
if need[i]<=0
then
begin
ans:=ans+sqrt(sqr(elevator[i].x-x)+sqr(elevator[i].y-y));
x:=elevator[i].x;
y:=elevator[i].y;
end
else
begin
for j:=1 to sum[i] do
f[1,j]:=sqrt(sqr(balloon[i,j].x-x)+sqr(balloon[i,j].y-y));
for k:=2 to need[i] do
begin
for j:=1 to sum[i] do
begin
f[k,j]:=maxlongint;
for p:=1 to sum[i] do
begin
if j<>p
then
f[k,j]:=min(f[k,j],f[k-1,p]+sqrt(sqr(balloon[i,j].x-balloon[i,p].x)+sqr(balloon[i,j].y-balloon[i,p].y)));
end;
end;
end;
minn:=maxlongint;
for j:=1 to sum[i] do
begin
minn:=min(minn,f[need[i],j]+sqrt(sqr(balloon[i,j].x-elevator[i].x)+sqr(balloon[i,j].y-elevator[i].y)));
end;
ans:=ans+minn;
x:=elevator[i].x;
y:=elevator[i].y;
end;
end;
write(ans:0:2);
end.
套用
仍然空洞的明日 是最接近黑的灰
无法成为任何东西 是最接近黑的灰
版权声明:本文标题:XYLX 10.19 天堂(HEAVEN) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1729778801a1212528.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论