柚子快報邀請碼778899分享：算法 java 蝸牛——藍(lán)橋杯
柚子快報邀請碼778899分享：算法 java 蝸?！{(lán)橋杯
蝸牛
題目分析
第一個階段定義dp數(shù)組
（1）縮小規(guī)模。我們要從第1根竹竿爬到第n根竹竿，那么規(guī)模就是這n根竹竿，dp[i]表示當(dāng)前爬到了第i根竹竿。
（2）考慮限制。
限制1，只能在x軸或者竹竿上爬行，在x軸上爬行速度為1單位每秒，在竹竿上向上和向下爬行的速度分別為0.7單位每秒和1.3單位每秒。
限制2，在第i和第i+1個竹竿間有傳送門，可以由第i根竹竿高度為
a
i
a_i
ai?的位置
(
x
i
,
a
i
)
(x_i,a_i)
(xi?,ai?)，瞬移到第i+1根竹竿高度為
b
i
+
1
b_{i+1}
bi+1?的位置
(
x
i
+
1
,
b
i
+
1
)
(x_{i+1},b_{i+1})
(xi+1?,bi+1?)。
對于一個蝸牛的在第i根竹竿上的位置有兩種狀態(tài)，要么是從x軸爬過來的，此時高度為0，要么是從第i-1個竹竿瞬移過來的，此時高度為
b
i
b_i
bi?。需要一個狀態(tài)表示此時蝸牛處在哪個位置，所以
d
p
[
i
]
[
0
]
dp[i][0]
dp[i][0]表示從x軸爬過來的，此時高度為0，
d
p
[
i
]
[
1
]
dp[i][1]
dp[i][1]表示從第i-1個竹竿瞬移過來的，此時高度為
b
i
b_i
bi?。
（3）定義dp數(shù)組
d
p
[
i
]
[
0
]
dp[i][0]
dp[i][0]表示從x軸爬過來的，此時高度為0，花費的時間。
d
p
[
i
]
[
1
]
dp[i][1]
dp[i][1]表示從第i-1個竹竿瞬移過來的，此時高度為
b
i
b_i
bi?，花費的時間。
第二個階段推導(dǎo)狀態(tài)轉(zhuǎn)移方程
d
p
[
i
]
[
0
]
=
m
i
n
(
d
p
[
i
?
1
]
[
0
]
+
x
[
i
]
?
x
[
i
?
1
]
,
d
p
[
i
?
1
]
[
1
]
+
b
[
i
]
/
1.3
)
dp[i][0]=min(dp[i-1][0]+x[i]-x[i-1],dp[i-1][1]+b[i]/1.3)
dp[i][0]=min(dp[i?1][0]+x[i]?x[i?1],dp[i?1][1]+b[i]/1.3)
d
p
[
i
?
1
]
[
0
]
+
x
[
i
]
?
x
[
i
?
1
]
dp[i-1][0]+x[i]-x[i-1]
dp[i?1][0]+x[i]?x[i?1]表示是從第i-1個竹竿從x軸爬過來的，那么消耗的時間就是x軸上的距離
x
[
i
]
?
x
[
i
?
1
]
x[i]-x[i-1]
x[i]?x[i?1]。
d
p
[
i
?
1
]
[
1
]
+
b
[
i
]
/
1.3
dp[i-1][1]+b[i]/1.3
dp[i?1][1]+b[i]/1.3表示是從第i-1個竹竿從x軸瞬移過來的，瞬移到高度為b[i]的地方，那么我要從那個地方下來，那么消耗的時間就是從y軸下來的距離
b
[
i
]
/
1.3
b[i]/1.3
b[i]/1.3。
i
f
(
a
[
i
]
>
b
[
i
]
)
if(a[i]>b[i])
if(a[i]>b[i])，如果是瞬移過來的，我要向上爬。
d
p
[
i
]
[
1
]
=
m
i
n
(
d
p
[
i
]
[
0
]
+
a
[
i
]
/
0.7
,
d
p
[
i
?
1
]
[
1
]
+
(
a
[
i
]
?
b
[
i
]
)
/
0.7
)
dp[i][1]=min(dp[i][0]+a[i]/0.7,dp[i-1][1]+(a[i]-b[i])/0.7)
dp[i][1]=min(dp[i][0]+a[i]/0.7,dp[i?1][1]+(a[i]?b[i])/0.7)
i
f
(
a
[
i
]
<
b
[
i
]
)
if(a[i] if(a[i] d p [ i ] [ 1 ] = m i n ( d p [ i ] [ 0 ] + a [ i ] / 0.7 , d p [ i ? 1 ] [ 1 ] + ( b [ i ] ? a [ i ] ) / 1.3 ) dp[i][1]=min(dp[i][0]+a[i]/0.7,dp[i-1][1]+(b[i]-a[i])/1.3) dp[i][1]=min(dp[i][0]+a[i]/0.7,dp[i?1][1]+(b[i]?a[i])/1.3) 第三個階段寫代碼 （1）dp數(shù)組的初始化 從(0,0)處開始爬，爬到第一個竹竿和第一個竹竿傳送門處的耗時如下。 double[][] dp = new double[n + 1][2]; dp[1][0] = x[1]; // 底端最小用時 dp[1][1] = x[1] + a[1] / 0.7; // 傳送門用時 （2）遞推dp數(shù)組 a.第一層for循環(huán)表示的是規(guī)模 c.第二層for循環(huán)表示的是dp數(shù)組的轉(zhuǎn)移點 只有兩個，不需要用for循環(huán) （3）表示答案 d p [ n ] [ 0 ] dp[n][0] dp[n][0] 題目代碼 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] x = new int[n+1]; int[] a = new int[n+1]; int[] b = new int[n+1]; for(int i = 1;i<=n;i++){ x[i] = sc.nextInt(); } for(int i = 1;i a[i] = sc.nextInt(); b[i+1] = sc.nextInt(); } double[][] dp = new double[n+1][2]; dp[1][0] = x[1]; dp[1][1] = x[1] + a[1]/0.7; for(int i = 2;i <= n;i++){ dp[i][0] = Math.min(dp[i-1][1] +b[i]/1.3 ,dp[i-1][0]+x[i]-x[i-1]); if(a[i]>b[i]){ dp[i][1] = Math.min(dp[i][0] + a[i]/0.7, dp[i-1][1] + (a[i]-b[i])/0.7); }else { dp[i][1] = Math.min(dp[i][0] + a[i]/0.7,dp[i-1][1] + (b[i]-a[i]) /1.3); } } System.out.printf("%.2f",dp[n][0]); sc.close(); } } 柚子快報邀請碼778899分享：算法 java 蝸?！{(lán)橋杯 推薦閱讀
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Bidorbuy競拍出海購
