COCI 2017/2018 Round #3,November 25th,2017 Retro

제목: 한 게임, n*m의 그림, 당신은 M의 위치에 있습니다. 매번 지도가 한 칸 내려갈 때마다 움직이지 않고 왼쪽으로 가거나 오른쪽으로 갈 수 있습니다. 한 걸음 한 걸음 공터, 폭탄, 또는 좌우 괄호를 만날 수 있습니다.마지막 줄에 가거나 폭탄을 맞으면 게임이 끝납니다.마지막으로 요구된 서열은 합법적인 괄호 서열로 가장 긴 사전 서열의 가장 작은 해를 구한다.
문제풀이: 우선 dp가 가장 긴 접미사의 길이를 정하고 dp[i][j][k]는 위치 i, j 접미사와 k일 때의 최장렬('('('-1을 표시하고')'은 +1)을 정의한다. 문자열을 복원할 때 bfs 초기 노드는 dp[dx][dy][sum]가 현재len과 같은지 여부를 판단하고 현재 bfs의 길이를 먼저 가야 한다.의 경우 다시 우선적으로'('의 상황, 마지막으로 가다')를 가면 답안의 사전 순서가 가장 작다는 것을 보증한다.
AC 코드:

#include
#include
#include
#include
#include
using namespace std;
char a[305][305];
struct node
{
	int x,y,sum,len;
	node(){}
	node(int x,int y,int sum,int len)
	{
		this->x=x;
		this->y=y;
		this->sum=sum;
		this->len=len;
	}
};
int dp[305][305][155],mark[305][305][155];
char ans[305];
int n,m;
int dir[3][2]={
	{1,-1},
	{1,0},
	{1,1}
};
priority_queueque; 
int val(char c)
{
	if(c=='.')return 2;
	if(c=='(')return 1;
	if(c==')')return 0;
}
bool operatorn||dy>m||dp[dx][dy][sum]!=len||a[dx][dy]=='*')continue;
			if(mark[dx][dy][sum])continue;
			mark[dx][dy][sum]=1;
			que.push(node(dx,dy,sum,len));
		}
	}
}
int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)	
		scanf("%s",a[i]+1);
	node s,e;
	s.len=s.sum=0;
	int mm=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]=='M')
				s.x=i,s.y=j;
	for(int i=1;i<=m;i++)
	{
		if(a[1][i]==')')dp[1][i][1]=1;
		if(a[1][i]=='.')dp[1][i][0]=0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]=='*')
				dp[i][j][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<=n/2;k++)
			{
				if(dp[i][j][k]==-1)continue;
				for(int f=0;f<3;f++)
				{
					int dx=i+dir[f][0];
					int dy=j+dir[f][1];
					if(a[dx][dy]=='*'||dx<=0||dy<=0||dx>n||dy>m)continue;
					if(a[dx][dy]=='('||a[dx][dy]==')')
					{
						if(a[dx][dy]==')')dp[dx][dy][k+1]=max(dp[dx][dy][k+1],dp[i][j][k]+1);
						if(a[dx][dy]=='('&&k!=0)dp[dx][dy][k-1]=max(dp[dx][dy][k-1],dp[i][j][k]+1);
					}
					else dp[dx][dy][k]=max(dp[dx][dy][k],dp[i][j][k]); 
				}
			}
	printf("%d
",dp[s.x][s.y][0]);
	que.push(node(s.x,s.y,0,dp[s.x][s.y][0]));
	mark[s.x][s.y][0]=1;
	bfs();
	for(int i=dp[s.x][s.y][0];i>=1;i--)
		printf("%c",ans[i]);
	printf("
");
}