結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー |
![]() |
提出日時 | 2020-05-25 01:51:00 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 1,550 bytes |
コンパイル時間 | 1,483 ms |
コンパイル使用メモリ | 161,908 KB |
実行使用メモリ | 12,124 KB |
最終ジャッジ日時 | 2024-10-12 18:00:57 |
合計ジャッジ時間 | 3,136 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.05.25 01:50:50**/#include "bits/stdc++.h"using namespace std;typedef long long ll;int main() {int t;cin >> t;for (int _ = 0; _ < t; _++) {string s;cin >> s;vector<int> dp1(s.size(),10000),dp2(s.size(),10000);int x_cnt = 0;for (int i = 3; i < s.size(); i++) {int cnt = 0;if (s[i-3] != 'g') cnt++;if (s[i-2] != 'o') cnt++;if (s[i-1] != 'o') cnt++;if (s[i] != 'd') cnt++;if (i >= 10) {if (s[i - 10] == 'p' &&s[i - 9] == 'r' &&s[i - 8] == 'o' &&s[i - 7] == 'b' &&s[i - 6] == 'l' &&s[i - 5] == 'e' &&s[i - 4] == 'm') {x_cnt++;}}dp1[i] = min(cnt+x_cnt,dp1[i-1]);}for (int i = s.size() - 7; i >= 0; i--) {int cnt = 0;if (s[i] != 'p') cnt++;if (s[i+1] != 'r') cnt++;if (s[i+2] != 'o') cnt++;if (s[i+3] != 'b') cnt++;if (s[i+4] != 'l') cnt++;if (s[i+5] != 'e') cnt++;if (s[i+6] != 'm') cnt++;dp2[i] = min(cnt,dp2[i+1]);}int ans = 10000;for (int i = 0; i < s.size() - 2; i++) {ans = min(ans,dp1[i] + dp2[i + 1]);}cout << ans << endl;}return 0;}