在經過一年的大學生活摧殘後,我發覺寫作業好難,寫題敘更難
不過活在2023年有個好處,那就是可以叫 ChatGPT 幫你把報告打好
然而這樣的缺點是 ChatGPT 經常有錯誤
因為你完全沒有在上課,所以你不知道 ChatGPT 寫的是不是對的
於是為了拿到分數,你決定讓 ChatGPT 生成一份報告後,再跟同學拿了一份他寫好的報告
你決定在 ChatGPT 生成好的報告中加上一些廢話,讓你的報告盡可能地貼近你同學的報告
然而寫太多廢話會讓你的報告看起來很奇怪又降低分數,於是你決定只加剛剛好的廢話讓你的報告跟你同學的一樣長
同時又不能讓你的報告跟你的同學的差太多(雖然太接近會被抓抄襲,不過加上那些廢話後助教應該抓不到)
具體來說,ChatGPT 寫的報告會是一個字串 $A$,同學的報告則是字串 $B$,其中 $|A| < |B|$。
你可以在 $A$ 當中填入一些 -
字元使 $|A| = |B|$,每次可以填入連續 $k$ 個這樣的字元,花費 $a+bk$。
而完成後的字串每有一個 $A_i \neq B_i$ 且 $A_i \neq$ -
,都會再花費 $c$。
請最小化花費
然後剛剛那個題敘好難懂所以我叫 ChatGPT 再幫我寫ㄌ一份
(我prompt打錯ㄌ,請不要參考圖內的題敘)
曾經有一個古老的城鎮,名叫字串城。這座城市以其奇特的建築和獨特的居民而聞名。城市的居民都是由字母所組成的字串,每個人都被賦予了一個特殊的名字。
在字串城的某一天,城市的魔法師提出了一個有趣的挑戰給城裡的居民。他們必須將自己的名字轉變成另一個居民的名字,但轉換過程中只能進行一項操作:在自己的名字中插入連續的 -
字元。
城市裡的居民都很興奮地接受了這個挑戰,每個人都有一個目標名字,希望能以最小的花費將自己的名字轉變成目標名字。然而,城市魔法師並沒有透露這個挑戰的具體花費方式,而是給予了一個數學模型。
在字串城的轉換過程中,每插入一段連續的 -
字元,都需要支付一筆費用。而這個費用由兩個參數決定:$a$ 和 $b$。插入 $k$ 個 -
字元的費用為 $a + bk$ 元。
此外,當最終轉換後的字串中的對應字元 $A_i$ 不等於 $B_i$ 且 $A_i$ 並不是 -
時,還需要支付額外的費用 $c$ 元。這表示,每當兩個字串中的對應位置有不同的字元時,都需要支付 $c$ 元。
第一行為一個字串 $A$
第二行為一個字串 $B$
第三行有三個正整數 $a, b, c$
$0 \leq a, b, c \leq 10 ^ 6$
$0 < |A| < |B| \leq 3000$
字串均由小寫英文字母組成
輸出一個正整數表示最小花費
以下是 3 個 Sample 的最佳填入法範例
1. -----ckefgisc------------
2. a--d
3. --abcd
No. | Testdata Range | Score |
---|