90分,W点1
查看原帖
90分,W点1
1037997
_TGWQ12_楼主2024/3/14 20:26
#include<bits/stdc++.h>
using namespace std;
const int N=2e2+5;
int a[5]; 
bool f[N][N][5];//f[i][j][k]表示[i~j]可由k变形而得 
bool b[5][5][5];//f[i][j][k]表示i可由jk变形而得到到
string s;
int zh(char a)
{
	if(a=='W')
		return 1;
	else if(a=='I')
		return 2;
	else if(a=='N')
		return 3;
	else if(a=='G')
		return 4;
}
char hui(int a)
{
	if(a==1)
		return 'W';
	else if(a==2)
		return 'I';
	else if(a==3)
		return 'N';
	else if(a==4)
		return 'G';
}
int main()
{

	cin>>a[1]>>a[2]>>a[3]>>a[4];
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=a[i];j++)
		{
			char c1,c2;
			cin>>c1>>c2;
			b[i][zh(c1)][zh(c2)]=1;
		}
	}
	cin>>s;
	int n=s.size();
	s=" "+s;
	for(int i=1;i<=n;i++)
	{
		f[i][i][zh(s[i])]=1;
	}
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)
			{
				for(int e=1;e<=4;e++)
					for(int h=1;h<=4;h++)
						for(int l=1;l<=4;l++)
						{
							if(b[e][h][l]&&f[i][k][h]&&f[k+1][j][l])
								f[i][j][e]=1;
						}
			}
		}
	}
	for(int i=1;i<=4;i++)
		if(f[1][n][i])
			cout<<hui(i);
	return 0;
}
/*
200000
*/
2024/3/14 20:26
加载中...