AOJ 0538 IOIOI
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538
解法
動的計画法を使う。
Oの数を数えることを意識して、
a[i] = if(s[i-1]=='I' && s[i]=='O' && s[i+1] == 'I') a[i-2] + 1 else 0
という漸化式を作り、aの中に何個N以上の数があるかしらべればよい。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_M = 1000000; int N, M; char s[MAX_M + 2]; int a[MAX_M + 2]; int main(){ while(scanf("%d", &N) && N != 0){ char c; s[0] = 'O'; s[M+1] = 'O'; fill(a, a + M + 1, 0); scanf("%d", &M); scanf("%c", &c); for(int i=0; i<M; i++) scanf("%c", s + i + 1); int ans = 0; for(int i=1; i<=M; i++){ if(s[i-1] == 'I' && s[i] == 'O' && s[i+1] == 'I'){ a[i] = a[i-2] + 1; if(a[i] >= N) ans++; } } printf("%d\n", ans); } return 0; }