====== سوال ۱۱ ======


در خانه‌ی پایین-چپ جدول زیر، یک لاک‌پشت قرار دارد و می‌خواهد به خانه‌ی بالا-راست برسد. روی هر خانه، ارتفاع آن نوشته شده است. لاک‌پشت در هر مرحله می‌تواند یک واحد به راست یا بالا برود و در هر گام، به اندازه‌ی اختلاف ارتفاع دو خانه خسته می‌شود (حتی اگر ارتفاع کم شود). کمینه‌ی مجموع میزان خستگی در مسیر چیست؟ 




{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:untitled2.png |}}



  - 2000
  - 3200
  - 3800
  - 1920
  - 2310


<پاسخ>
 گزینه‌ی ۴ درست است.


اگر
$b[i][j]$
برابر ارتفاع خانه‌ی واقع در سطر $i$ و ستون $j$ و هم‌چنین
$a[i][j]$
برابر کم‌ترین میزان خستگی لاک‌پشت برای رسیدن از مبدأ به  این خانه باشد، داریم:
$$a[i][j] = min\Big(\big|b[i][j] - b[i -  1][j]\big| + a[i - 1][j], \big|b[i][j]-b[i][j-1]\big| + a[i][j - 1] \Big)$$
این رابطه با بررسی دو حالت ورود به خانه‌ی مذکور گفته شده است (از چپ یا پایین). حال با به دست آوردن مقادیر $a[i][j]$ به صورت پویا، مقادیر زیر به دست می‌آید:

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:untitled3.png |}}


پس پاسخ برابر ۱۹۲۰ است.


</پاسخ>

  * [[سوال ۱۰|سوال قبل]]
  * [[سوال ۱۲|سوال بعد]]