【BZOJ1028】【JSOI2007】麻将 暴力
浏览数：42 /
时间：2015年06月09日
转载请注明出处谢谢：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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
