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;
}