[codeforces] 1150D. Three Religions

문제

https://codeforces.com/contest/1150/problem/D

Problem - D - Codeforces

 

풀이

3차원 dp를 이용하여 해결한다.

쿼리 형의 문제가 아니라 일반적인 DP라고 생각하고, 모든 문자가 미리 다 들어와있다고 가정하고 문제를 먼저 풀자.

 

$dp(i,j,k)$ = 1번, 2번 3번 religion description이 각각 i글자, j글자, k글자일 때, 필요한 Word of Universe의 최소길이

 

라고 정의하자. 

그러면 $dp(i,j,k)$는 $dp(i-1,j,k)$에서 한글자가 추가된 경우와, $dp(i,j-1,k)$에서 한글자가 추가된 경우, $dp(i,j,k-1)$에서 한글자가 추가된 경우. 이 세가지의 경우 중에서 가장 작은 경우의 답이 된다.

각 케이스는 서로 대칭이므로 첫 번째 케이스만 보자.

 

현재 $dp(i-1,j,k)$만큼의 Word of Universe를 사용하고 있다.

이 때 새로운 글자 c가 추가될 때 $dp(i,j,k)$는 Word of Universe 위에서 $dp(i-1,j,k)$ 이후에 나타나는 가장 가까운 c의 위치가 된다.

 

따라서 이를 빠르게 계산하기 위해서 $nx(i,j)$라는 배열을 만드는데 $nx(i,j)$는 Word of Universe 상에서 i+1~끝까지 배열에서 가장 가까운 알파벳 j의 위치이며, 이를 미리 만드는데에는 $O(n * |A|)$이면 충분하다. ($|A|$는 사용하는 알파벳의 개수) 

 

따라서, 이 nx를 이용해서 dp 관계식을 엄밀히 세워보면 다음과 같다.

$$dp(i,j,k)=\min(nx(dp(i-1,j,k), des_1(i-1)), nx(dp(i,j-1,k), des_2(j-1)), nx(dp(i,j,k-1), des_3(k-1)))$$

단, $des_i$는 i 종교의 description 목록이다.

 

이 점화식을 바탕으로 dp배열을 구현한다.

+ query가 들어올 경우 해당하는 글자를 하나 늘리고, 해당 글자가 늘어나서 값이 추가되는 부분만 새로 구해주면 된다. 이 부분의 개수는 쿼리 한 번에 $O(n^2)$이다.

 

- query가 들어올 경우 단순히 description 개수만 한개 빼주면 된다. 이미 채워져있는 테이블은 무시한다.

 

 

Time Complexity : $O(n|A|+qn^2)$

 

코드

#include <iostream>
#include <vector>
#include <string>

#define INF 1<<30
#define N 251
#define L 100010
#define A 26
using namespace std;

string wou;
int n,q;
int nx[L][A], p[A];
int dp[N][N][N], len[4], pre[4];
char des[4][L];

int main()
{
	cin>>n>>q>>wou;
	wou=" "+wou;
	for(int i=0;i<26;i++)
	{
		nx[n+1][i]=n+1;
		p[i]=n+1;
	}
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<26;j++) nx[i][j]=p[j];
		if(i) p[wou[i]-'a'] = i;
	}

	while(q--)
	{
		string type,c;
		int x;
		cin>>type>>x;

		for(int i=1;i<4;i++) pre[i]=0;
		if(type[0]=='-')
		{
			len[x]--;
			cout<< (dp[len[1]][len[2]][len[3]]<=n?"YES":"NO")<<"\n";
			continue;
		}
		cin>>c;
		pre[x] = len[x];
		des[x][len[x]++] = c[0];

		for(int i=pre[1];i<=len[1];i++) for(int j=pre[2];j<=len[2];j++) for(int k=pre[3];k<=len[3];k++)
		{
			if(i==0 && j==0 && k==0)continue;
			dp[i][j][k] = INF;
			if(i) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i-1][j][k] ][ des[1][i-1]-'a' ]);
			if(j) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i][j-1][k] ][ des[2][j-1]-'a' ]);
			if(k) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i][j][k-1] ][ des[3][k-1]-'a' ]);	
		}
		cout<< (dp[len[1]][len[2]][len[3]]<=n?"YES":"NO")<<"\n";
	}
}