题目描述
就是给你一副牌，问你最少几次能出完。
详细规则见规则
(nleq 23)
题解
NOIP的数据非常水，错误一大堆的程序都能AC。
因为顺子对答案的影响最大，所以先枚举顺子进行搜索。
接下来网上很多的程序都直接计算答案了。实际上还要进行一次搜索，枚举拆牌的方案，有以下几种：
1.一组四张牌可以拆成两组两张牌
2.一组四张牌可以拆成一组一张牌+一组三张牌
3.一组三张牌可以拆成一组一张牌+一组两张牌
4.一组两张牌可以拆成两组一张牌
5.一对王可以拆成两组一张牌
然后就可以计算方案。
加个最优性剪枝就可以过了。
时间复杂度：(O(???))
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int s[20];
int a[20],c[20];
int ans,n;
int calc2()
{
int res=0;
memcpy(c,a,sizeof a);
while(c[4]&&c[2]>=2)
{
c[4]--;
c[2]-=2;
res++;
}
while(c[4]&&c[1]>=2)
{
c[4]--;
c[1]-=2;
res++;
}
while(c[3]&&c[2])
{
c[3]--;
c[2]--;
res++;
}
while(c[3]&&c[1])
{
c[3]--;
c[1]--;
res++;
}
return res+c[1]+c[2]+c[3]+c[4];
}
int calc()
{
int ans=calc2();
if(a[4])
{
a[4]--;
a[2]+=2;
ans=min(ans,calc());
a[4]++;
a[2]-=2;
}
if(a[4])
{
a[4]--;
a[3]++;
a[1]++;
ans=min(ans,calc());
a[4]++;
a[3]--;
a[1]--;
}
if(a[3])
{
a[3]--;
a[1]++;
a[2]++;
ans=min(ans,calc());
a[1]--;
a[2]--;
a[3]++;
}
if(a[2])
{
a[2]--;
a[1]+=2;
ans=min(ans,calc());
a[1]-=2;
a[2]++;
}
return ans;
}
int calc3()
{
int i;
memset(a,0,sizeof a);
int res=0;
if(s[0]>=2)
res++;
else if(s[0]==1)
a[1]++;
for(i=1;i<=13;i++)
a[s[i]]++;
res+=calc();
memset(a,0,sizeof a);
for(i=1;i<=13;i++)
a[s[i]]++;
a[1]+=s[0];
return min(res,calc());
}
void dfs(int now)
{
if(now>=ans)
return;
int v=calc3();
ans=min(ans,now+v);
int i,j,k;
for(i=2;i<=13;i++)
{
j=i;
while(j<=13&&s[j]>=3)
{
j++;
if(j-i>=2)
{
for(k=i;k<=j-1;k++)
s[k]-=3;
dfs(now+1);
for(k=i;k<=j-1;k++)
s[k]+=3;
}
}
}
for(i=2;i<=13;i++)
{
j=i;
while(j<=13&&s[j]>=2)
{
j++;
if(j-i>=3)
{
for(k=i;k<=j-1;k++)
s[k]-=2;
dfs(now+1);
for(k=i;k<=j-1;k++)
s[k]+=2;
}
}
}
for(i=2;i<=13;i++)
{
j=i;
while(j<=13&&s[j]>=1)
{
j++;
if(j-i>=5)
{
for(k=i;k<=j-1;k++)
s[k]-=1;
dfs(now+1);
for(k=i;k<=j-1;k++)
s[k]+=1;
}
}
}
for(i=2;i<=13;i++)
if(s[i]==4)
{
s[i]-=4;
for(j=i+1;j<=13;j++)
if(s[j]==4)
{
s[j]-=4;
dfs(now+2);
s[j]+=4;
}
s[i]+=4;
}
}
void solve()
{
int x,y;
memset(s,0,sizeof s);
int i;
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(x==1)
x=13;
else if(x)
x--;
s[x]++;
}
ans=0x7fffffff;
dfs(0);
printf("%d
",ans);
}
int main()
{
int t;
scanf("%d%d",&t,&n);
while(t--)
solve();
return 0;
}