ncpc2016 C Gym 101550C

まず4色、異なる順序、上昇と下降を考えて、検索で列挙することができて、それから現在のこのカードの目標がdfsで出た順序の最終的な状況がどれだけあるべきかを知ることができます.
次は巧みな考えで、勝手にカードを引いてどこにでも移動できる以上、操作するたびに必ず最後の位置に挿入します.では動かないカードは本来相対的な位置が正しいカードです.
相対位置の正確さは古典的なlcs問題の2次元DPによって解決することができ,最初の状況と最終状況をlcsすると,最長共通サブシーケンスは相対位置の正確なカードである.答えはn-ansです.

#include
#include
#include
#define maxl 60

using namespace std;

int n,ans;
int up[5],ord[5];
int num[maxl];
int a[maxl],b[maxl],ini[maxl];
int f[maxl][maxl];
int l[5]={0,1,14,27,40};
int r[5]={0,13,26,39,52};
char ch[maxl];
bool in[maxl];

inline void prework()
{
	int x;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ch);
		if(ch[0]>='2' && ch[0]<='9')
			x=ch[0]-'2'+1;
		else if(ch[0]=='T')
			x=9;
		else if(ch[0]=='J')
			x=10;
		else if(ch[0]=='Q')
			x=11;
		else if(ch[0]=='K')
			x=12;
		else
			x=13;
		if(ch[1]=='h')
			x+=13;
		else if(ch[1]=='d')
			x+=26;
		else if(ch[1]=='c')
			x+=39;
		ini[i]=x;
	}
}

inline void calc()
{
	int left,right;
	for(int i=1;i<=4;i++)
	{
		if(up[ord[i]]==1)
		{
			left=l[ord[i]];
			for(int j=(i-1)*13+1;j<=i*13;j++)
				num[j]=left++;
		}
		else
		{
			right=r[ord[i]];
			for(int j=(i-1)*13+1;j<=i*13;j++)
				num[j]=right--;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=52;j++)
		if(ini[i]==num[j])
			a[i]=j;
	for(int i=1;i<=n;i++)
		b[i]=a[i];
	sort(b+1,b+1+n);
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(a[i]==b[j])
				f[i][j]=f[i-1][j-1]+1;
			f[i][j]=max(f[i][j],f[i-1][j]);
			f[i][j]=max(f[i][j],f[i][j-1]);
		}
	ans=max(ans,f[n][n]);
}

void dfs(int k)
{
	for(int i=1;i<=4;i++)
	if(!in[i])
	{
		ord[k]=i;in[i]=true;
		up[i]=1;
		if(k==4)
			calc();
		else
			dfs(k+1);
		up[i]=0;
		up[i]=2;
		if(k==4)
			calc();
		else
			dfs(k+1);
		up[i]=0;
		ord[k]=0;in[i]=false;
	}
}

inline void mainwork()
{
	ans=0;
	memset(in,false,sizeof(in));
	dfs(1);
}

inline void print()
{
	printf("%d
",n-ans);
}

int main()
{
	while(~scanf("%d",&n))
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}