柚子快報(bào)激活碼778899分享：算法 藍(lán)橋杯：蝸牛（Java）

http://yzkb.51969.com/

目錄

題目描述：輸入格式輸出格式代碼實(shí)現(xiàn)：

題目描述：

這天，一只蝸牛來到了二維坐標(biāo)系的原點(diǎn)。 在α軸上長有n根竹竿。它們平行于y軸，底部縱坐標(biāo)為0，橫坐標(biāo)分別為a1, a2, …, n。竹竿的高度均為無跟高，寬度可忽略。蝸牛想要從原點(diǎn)走到第n個(gè)竹竿的底部也就是坐標(biāo)(xn,0)。它只能在α軸上或者竹竿上爬行，在α軸上爬行速度為1單位每秒;由于受到引力影響，蝸牛在竹竿上向上和向下爬行的速度分別為0.7單位每秒和1.3單位每秒。 為了快速到達(dá)目的地，它施展了魔法，在第i和i＋1根竹竿之間建立了傳送門(0

x

i

+

1

x_{i+1}

xi+1?,

b

i

+

1

b_{i+1}

bi+1?)，請(qǐng)計(jì)算蝸牛最少需要多少秒才能到達(dá)目的地。

輸入格式

輸入共1＋n行，第一行為一個(gè)正整數(shù)n; 第二行為n個(gè)正整數(shù)c1, 2, …, n ; 后面n―1行，每行兩個(gè)正整數(shù)ai,bi+1。

3

1 10 11

1 1

2 1

輸出格式

輸出共一行，一個(gè)浮點(diǎn)數(shù)表示答案(四舍五入保留兩位小數(shù))。

4.20

代碼實(shí)現(xiàn)：

import java.util.Scanner;

public class Main{

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

// 在此輸入您的代碼...

int n = scan.nextInt();// n根竹竿

int[] arr = new int[n];// 存儲(chǔ)每個(gè)橫坐標(biāo)的值

for (int i = 0; i < arr.length; i++) {

arr[i] = scan.nextInt();

}

// 記錄坐標(biāo)兩兩之間的傳送點(diǎn)的對(duì)應(yīng)位置

// 共有n-1組數(shù)據(jù)：0表示傳送門1的高度a，1表示傳送門2的高度b

int[][] transmit = new int[n][2];

for (int i = 0; i < n - 1; i++) {

transmit[i][0] = scan.nextInt();

transmit[i][1] = scan.nextInt();

}

// dp[i][0]表示到達(dá)第i個(gè)坐標(biāo)的最短時(shí)間,dp[i][1]表示到達(dá)第i個(gè)傳送們的最短時(shí)間

double[][] dp = new double[n + 1][2];

// 計(jì)算第一組dp值

dp[1][0] = arr[0];// 橫坐標(biāo)距離

dp[1][1] = arr[0] + transmit[0][0] / 0.7;// 橫坐標(biāo)距離 + 向上爬到傳送門距離

int a, b;

// 動(dòng)態(tài)規(guī)劃：打表遍歷獲得dp的值

for (int i = 2; i <= n; i++) {

a = transmit[i - 1][0];// 下一次傳送門的高度

b = transmit[i - 2][1];// 當(dāng)前傳送之后的高度

int pos = arr[i - 1] - arr[i - 2];// 距離下一個(gè)坐標(biāo)點(diǎn)的距離

if (a > b) {

// 傳送之后比下一次傳送的位置更低

dp[i][1] = Math.min(dp[i - 1][0] + pos + a / 0.7, dp[i - 1][1] + (a - b) / 0.7);

// 計(jì)算走傳送路徑的最短時(shí)間：比較兩種情況

// 一，上一輪到達(dá)坐標(biāo)點(diǎn)的時(shí)間 + 到達(dá)下一個(gè)坐標(biāo)點(diǎn)的距離 + 向上爬行到傳送門的距離

// 二，上一輪到達(dá)傳送門的距離 + 向上爬行到下一次傳送的距離

} else {

// 傳送之后比下一次傳送的位置更高或者等高

dp[i][1] = Math.min(dp[i - 1][0] + pos + a / 0.7, dp[i - 1][1] + (b - a) / 1.3);

// 與上面判斷不同的是：第二種情況需要向上爬行到指定傳送位置

}

// 計(jì)算到達(dá)坐標(biāo)軸的時(shí)間

dp[i][0] = Math.min(dp[i - 1][1] + b / 1.3, dp[i - 1][0] + pos);// 分為兩種情況

// 情況一：剛傳送過來可能不在坐標(biāo)點(diǎn)上，上一輪傳送時(shí)間 + 向下爬行的時(shí)間

// 情況二：剛好在坐標(biāo)點(diǎn)上，上一輪到達(dá)坐標(biāo)點(diǎn)時(shí)間 + 到達(dá)下一個(gè)坐標(biāo)點(diǎn)的距離

}

System.out.printf("%.2f", dp[n][0]);// 輸出最后一輪到達(dá)坐標(biāo)點(diǎn)的時(shí)間

scan.close();

}

}

柚子快報(bào)激活碼778899分享：算法 藍(lán)橋杯：蝸牛（Java）

http://yzkb.51969.com/

精彩內(nèi)容