切換
舊版
前往
大廳
主題

ZeroJudge - e984: 連假時在做什麼？有沒有空？可以來打code嗎？　解題心得

Not In My Back Yard | 2020-05-01 01:42:02 | 巴幣 2 | 人氣 369
題目連結：
題目大意：
給定一正整數 K （K ≦ 10 ^ 6），求第 K 個 LunlunNumber 為何？

LunlunNumber 定義如下：
一正整數 X 其在十進位下的表示法中，每一位數與前面和後面（如果該位有前後的位數的話）的差皆不超過 1 。 X 即為 LunlunNumber 。

範例輸入：
範例輸入一：
1

範例輸入二：
15

範例輸入三：
100000
範例輸出：
範例輸出一：
1

範例輸出二：
23

範例輸出三：
3234566667
解題思維：
本人在解題網站的討論區已經有 PO 出詳解，參見這裡。

不過其中有一句：
「而當中有哪些是合法的 LunlunNumber 呢？答案是為 Dn - 1 、Dn 、 Dn + 1 的那幾個數字。」為了避免誤會，再補充一下「答案為」緊接著的表語應為「新接的頭」。

所以實際上是「答案是新接的頭（即數字開頭）為 Dn - 1 、Dn 、 Dn + 1 的那幾個數字。」
而非指 Dn - 1 、Dn 、 Dn + 1 本身是答案。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#動態規劃（Dynamic Programming）
留言

創作回應

胖胖貓
LunlunNumber 的數量不多( 1e6個 )，我直接做 BFS 狀態展開，Queue 裡面最多 3e6 個。
https://pse.is/S45SB
不過當 Ｋ 極大時確實需要靠 動態規劃計算個數
2020-05-01 10:35:20
追蹤 創作集

作者相關創作

作品資料夾

更多創作

追蹤 創作集
其他創作
作品資料夾