JOI 2009 春合宿 day1-2 「Stamp」
貪欲法でお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; }