NOIP 2014【斗地主】

这真是道大火题。

因为保证数据随机，所以开始很多人直接用搜索 + 贪心水过去了，后来，为了遏制骗分这种不良风气的传播，各大 OJ 相继推出了斗地主加强版……

正解：

先爆搜顺子，枚举打或不打，打多少张。对于剩下的散牌做 DP，最少需要多少次打完。

设 \(f[i][j][k][l]\) 表示四张牌的剩 \(i\) 张，三张牌的剩 \(j\) 张，两张牌的剩 \(k\) 张，一张牌的剩 \(l\) 张，最少需要多少次打完。因为不考虑打顺子，所以点数与打完的次数无关。然后按照题目除顺子之外的打法转移即可。

与加强版的区别就是网能不能看成普通对子。

注意

记忆化搜索的值莫名其妙的变化了多半是数组越界。

搜索不要没想清楚就随便剪枝，可能不知不觉中就剪挂了。

代码是加强版的。

#include <bits/stdc++.h>

using namespace std;

#define N 25

#define RG register

inline int gi()

{

	RG int ret; RG char ch;

	ret=0, ch=getchar();

	while (ch < '0' || ch > '9')

		ch=getchar();

	while (ch >= '0' && ch <= '9')

		ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();

	return ret;

}

int tong[N],f[N][N][N][N];

int ans,n;

inline int cal(int i,int j,int k,int l)

{

	if (f[i][j][k][l] || (!i && !j && !k && !l))

		return f[i][j][k][l];

	RG int ret;

	ret=i+j+k+l;

	if (i)

		ret=min(ret,min(cal(i-1,j+1,k,l+1),cal(i-1,j,k+2,l)));

	if (j)

		ret=min(ret,cal(i,j-1,k+1,l+1));

	if (k)

		ret=min(ret,cal(i,j,k-1,l+2));

	if (i && k > 1)

		ret=min(ret,cal(i-1,j,k-2,l)+1);

	if (i && l > 1)

		ret=min(ret,cal(i-1,j,k,l-2)+1);

	if (j && k)

		ret=min(ret,cal(i,j-1,k-1,l)+1);

	if (j && l)

		ret=min(ret,cal(i,j-1,k,l-1)+1);

	return f[i][j][k][l]=ret;

}

inline void dfs(int dep)

{

	if (dep >= ans)

		return;

	RG int i,j,k,l,tot;

	for (i=3; i<11; ++i)

		{

			if (!tong[i])

				continue;

			tot=1, j=i+1;

			while (tong[j])

				tot++, j++;

			if (tot < 5)

				continue;

			for (j=5; j<=tot; ++j)

				{

					for (k=0; k<j; ++k)

						tong[i+k]--;

					dfs(dep+1);

					for (k=0; k<j; ++k)

						tong[i+k]++;

				}

		}

	for (i=3; i<13; ++i)

		{

			if (tong[i] < 2)

				continue;

			tot=1, j=i+1;

			while (tong[j] >= 2)

				tot++, j++;

			if (tot < 3)

				continue;

			for (j=3; j<=tot; ++j)

				{

					for (k=0; k<j; ++k)

						tong[i+k]-=2;

					dfs(dep+1);

					for (k=0; k<j; ++k)

						tong[i+k]+=2;

				}

		}

	for (i=3; i<14; ++i)

		{

			if (tong[i] < 3)

				continue;

			tot=1, j=i+1;

			while (tong[j] >= 3)

				tot++, j++;

			if (tot < 2)

				continue;

			for (j=2; j<=tot; ++j)

				{

					for (k=0; k<j; ++k)

						tong[i+k]-=3;

					dfs(dep+1);

					for (k=0; k<j; ++k)

						tong[i+k]+=3;

				}

		}

	i=j=k=l=0;

	for (tot=2; tot<15; ++tot)

		if (!tong[tot])

			continue;

		else if (tong[tot] == 1)

			l++;

		else if (tong[tot] == 2)

			k++;

		else if (tong[tot] == 3)

			j++;

		else if (tong[tot] == 4)

			i++;

	if (tong[0] == 2)

		ans=min(ans,dep+cal(i,j,k,l)+1);

	l+=tong[0];

	// if (tong[0] == 2)

	// 	k++;

	// else if (tong[0] == 1)

	// 	l++;

	ans=min(ans,dep+cal(i,j,k,l));

}

inline void work()

{

	RG int i,x;

	for (i=1; i<=n; ++i)

		x=gi(), tong[x]++, x=gi();

	tong[14]=tong[1];

	ans=n;

	dfs(0);

	printf("%d\n",ans);

	for (i=0; i<15; ++i)

		tong[i]=0;

}

int main()

{

	RG int t;

	t=gi(), n=gi();

	while (t--)

		work();

	return 0;

}

巴特西

NOIP 2014【斗地主】

最新文章

热门文章