結果

問題 No.910 素数部分列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:37:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 983 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 92,672 KB
最終ジャッジ日時 2025-06-12 16:37:49
合計ジャッジ時間 9,373 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    s = input[1]

    # 预处理由1和9组成的素数字符串集合
    primes_rest = {
        "11", "19", "91", "111", "199", "911", "11911", "11111", "1111111111111111111", "11111111111111111111", "111111111111111111111"
    }

    # 统计3、5、7的数量
    count = 0
    s_rest = []
    for c in s:
        if c in {'3', '5', '7'}:
            count += 1
        else:
            s_rest.append(c)
    s_rest = ''.join(s_rest)
    m = len(s_rest)

    # 动态规划
    dp = [0] * (m + 1)
    for i in range(1, m + 1):
        dp[i] = dp[i-1]
        for length in range(2, 19):
            if i >= length:
                substr = s_rest[i-length:i]
                if substr in primes_rest:
                    if dp[i-length] + 1 > dp[i]:
                        dp[i] = dp[i-length] + 1

    additional = dp[m]
    print(count + additional)

if __name__ == "__main__":
    main()
0