結果
問題 |
No.910 素数部分列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:34:04 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 983 bytes |
コンパイル時間 | 426 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 92,544 KB |
最終ジャッジ日時 | 2025-06-12 16:34:40 |
合計ジャッジ時間 | 9,420 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 WA * 39 |
ソースコード
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()