ZeroJudge 解題筆記：k518. P6.蛋糕切塊 (Cake)

作者：王一哲
日期：2025年5月3日



ZeroJudge 題目連結：k518. P6.蛋糕切塊 (Cake)

解題想法

這題考動態規畫，我同時利用 set 儲存可用的子字串，這樣程式運作速度會比較快。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 3.4 MB，通過測試。

import sys

def can_cut_cake(s, cuts):
    n = len(s)  # 字串長度
    dp = [False]*(n+1)  # 是否能走到 i，如果能走到 i+1 代表有解
    dp[0] = True  # 一定能走到開頭
    # 動態規劃遍歷
    for i in range(1, n+1):  # 依序找終點 i = 1 ~ n
        for j in range(i):  # 依序找起點 j = 0 ~ i-1
            if dp[j] and s[j:i] in cuts:  # 如果能走到 j 而且 s[j:i] 在 cuts 之中
                dp[i] = True  # 可以走到 i
                break  # 只要找到一個可行切割後就可以停止
    print("yes" if dp[n] else "no")  # 如果 dp[n] 為 True 印出 yes，反之印出 no

for s in sys.stdin:
    s = s.strip()  # 要檢查的字串
    m = int(input())  # 可用的子字串數量
    cuts = set()  # 可用的子字串
    for _ in range(m): cuts.add(input())  
    can_cut_cake(s, cuts)  # 計算並輸出結果

C++ 程式碼

使用時間約為 71 ms，記憶體約為 544 kB，通過測試。

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

void can_cut_cake(string s, set<string> cuts) {
    int n = (int)s.size();  // 字串長度
    bool dp[n+1] = {0};
    dp[0] = true;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<i; j++) {
            if (dp[j] && cuts.count(s.substr(j, i-j)) == 1) {
                dp[i] = true; break;
            }
        }
    }
    cout << (dp[n] ? "yes\n" : "no\n");
    return;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;  // 要檢查的字串
    while(cin >> s) {
        int m; cin >> m;  // 可用的子字串數量
        set<string> cuts;  // 可用的子字串
        for(int i=0; i<m; i++) {
            string t; cin >> t;
            cuts.insert(t);
        }
        can_cut_cake(s, cuts);
    }
    return 0;
}