Codeforces Round #109 (Div. 1) A : Hometask

問題概要

長さL(<10^5)の文字列がある。また、K(<13)個の長さ2の禁止文字列がある。禁止文字列が出現しないようにするには最小で何文字削れば良いか求める問題。

解法

何だか謎の制約があるらしいけど無視してDPで解く。文字列の先頭から考えて、dp[i][j] = (i文字目まで見て、残っている直前の文字がjであるような最小コスト)とすると十分間に合う。

acceptされたコード

計算量O(L*K*Σ)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_L = (int)(1e5);
const int MAX_K = 13;
const int INF = 1<<29;

int K;
char buf[MAX_L + 1];
char taboo[MAX_K][5];
int dp[MAX_L + 1][27];

void init(){
	scanf(" %s ", buf);
	scanf("%d ", &K);
	for(int i=0; i<K; i++){
		scanf(" %s ", taboo[i]);
	}
}

int solve(){
	const int L = strlen(buf);

	for(int i=0; i<=L; i++){
		for(int j=0; j<27; j++){
			dp[i][j] = INF;
		}
	}

	dp[0][26] = 0;

	for(int i=0; i<L; i++){
		for(int j=0; j<27; j++)if(dp[i][j] < INF){
			bool match = false;
			for(int k=0; k<K; k++){
				match |= (taboo[k][0]-'a' == j && taboo[k][1] == buf[i]);
				match |= (taboo[k][1]-'a' == j && taboo[k][0] == buf[i]);
			}
			if(!match){
				dp[i+1][buf[i]-'a'] = min(dp[i+1][buf[i]-'a'], dp[i][j]);
			}
			dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
		}
	}
	return *min_element(dp[L], dp[L]+26);
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}