【BZOJ1028】【JSOI2007】麻将 暴力

转载请注明出处谢谢:http://blog.csdn.net/vmurder/article/details/42921985

题目大意: 给你一副牌,问是否是听牌(即再加一张牌能“胡”),如果是,输出摸到哪些牌能胡,不是输出“NO”

胡牌规则: 首先需要有两个相同数字的牌被消掉,然后可以将三张相同的牌消掉,也可以将三张连续标号的牌消掉,消没即胡。

比如 22 444555 789就是胡牌。

题解:

暴力枚举再摸到哪张牌就能胡,

然后暴力消牌。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50100
#define mod 10007
#define inf 0x3f3f3f3f
using namespace std;
int sk[N],sum[N],n,m;
bool check(int mid)
{
	int use=0,i,j,len=0;
	for(i=1;i<=n;i++)
	{
		len+=sk[i];
		if(len+sk[i+1]>mid)use++,len=0;
	}
	if(use>m)return 0;
	else return 1;
}
int f[2][N];
int now,last;
int main()
{
	freopen("test.in","r",stdin);
	int i,j,k;
	int l=0,r=0,mid,ans;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&sk[i]);
		sum[i]=sum[i-1]+sk[i];
		l=max(l,sk[i]),r+=sk[i];
	}
	while(l<r)
	{
		if(r-l<=3)
		{
			for(i=r;i>=l;i--)if(check(i))ans=i;
			break;
		}
		mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d ",mid=ans),ans=0;
	f[now=1][0]=1;
	int top;
	for(i=1;i<=m+1;i++)
	{
		now^=1,last^=1;
		k=0,top=i-2;
		for(j=i;j<=n;j++)
		{
			k+=f[last][j-1],k%=mod;
			while(sum[j]-sum[top+1]>mid)
			{
				k-=f[last][++top];
				if(k<0)k+=mod;
			}
			f[now][j]=k;
		}
		ans+=f[now][n],ans%=mod;
	}
	printf("%d\n",ans);
	return 0;
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。