読者です 読者をやめる 読者になる 読者になる

JOI 2009 春合宿 day1-2 「Stamp」

JOI

貪欲法でおk。
「削除」をするよりも、「挿入」もしくは、2文字増やして「入れ替える」方が良い。
端に注意。

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;



int main(){
	bool f = true;
	int n, len = 0, x = 0, y = 0;
	char a, b = 'O';
	
	scanf("%d ", &n);
	
	rep(i,n){
		scanf("%c", &a);
		
		if(a == b){
			len++;
		} else {
			if(f){
				x += (len+1)/2;
				y += len/2;
				f = false;
			} else{
				x += len/2;
				y += (len + ((b=='I')?-1:1))/2;
			}
			
			b = a; len = 1;
		}
	}
	
	x += (len + ((b=='I')?0:1))/2;
	y += (len + ((b=='I')?-1:0))/2;
	
	
	printf("%d\n%d\n",x,y*2+1);
	
	return 0;
}