kojingharangの日記

Codeforces #139 Div2 C - Barcode

22:32 |

• # か . が書いてあるグリッドがある。これを同じ色の幅が X～Y なバーコードにするために書き換える必要のあるマスの個数の最小値を求める。
• W,H,X,Y ≦ 1000

• DP筋を鍛えるシリーズ

（あとで）

• dp[col][x] : x 列含めて左側の全セルが無矛盾であるように x 列を色 col(0or1) で塗った時の書き換えセル数の最小値
• とすると
• X～Y なる i について、今みてる列から i 列前は（もしあれば）今と違う色で、その次 x-i+1 列から今の列は全部今の色
• じゃないといけないので
• dp[col][x] = min(dp[1-col][x-i] + (Σj列を全部colに塗るときの書き換え回数 for j in [x-i+1, x]) for i in [X, Y])
• ただし最初のしましまの太さも X～Y じゃなきゃいけないので x-i+1≧0 のときだけ更新する必要がある
• min(dp[0][W-1], dp[1][W-1]) が答え

• X=2, Y=4 の場合
• ？■□□□今
• ？？■□□今
• ？？？■□今

↓あとで (accepted in practice)

#define INF (1<<30)

int dp[2][1010];

int main() {
	ll H,W,X,Y;
	while(cin>>H>>W>>X>>Y) {
		REP(col, 2) REP(x, 1010) dp[col][x]=INF;
		
		VVI co(2, VI(W));
		REP(i, H) {
			string s;
			cin>>s;
			REP(x, s.size()) co[0][x]+=s[x]=='.', co[1][x]+=s[x]!='.';
		}
		REP(x, W) {
			REP(col, 2) {
				RANGE(i, X, Y+1) {
					int v = 0;
					if(x-i>=0) v += dp[1-col][x-i];
					if(x-i+1>=0) {
						RANGE(j, x-i+1, x+1) v += co[col][j];
						dp[col][x] = min(dp[col][x], v);
					}
				}
			}
		}
		
		cout<<min(dp[0][W-1], dp[1][W-1])<<endl;
	}
	
	return 0;
}

ツイートする