题目分析

错误解法1:搜索顺子,剩下的牌分成有1张,有2张,有3张,有4张。然后4张组尽可能带1张和2张,再用3张组带1张和2张。
HACK数据1

1 8
3 1
3 1
3 1
3 1
4 1
4 1
4 1
4 1

正确答案:1
我的答案:2
错误解法2:特判了错误解法1里面的情况。
HACK数据2

1 22
5 1
5 1
5 1
5 1
9 1
9 1
12 1
12 1
12 1
10 1
11 1
11 1
11 1
11 1
2 1
2 1
2 1
3 1
6 1
6 1
6 1
8 1

正确答案:4
我的答案:5
错误解法3:于是我就觉得如果遇到1张单牌1个对子1个三牌2个四张的情况,就这么组合出最优,然后我就这么写了。
HACK数据3

1 17
5 1
5 1
5 1
5 1
9 1
9 1
12 1
12 1
12 1
10 1
11 1
11 1
11 1
11 1
3 1
3 1
4 1

正确答案:3
我的答案:4
正确解法
先搜索顺子,然后再搜一次,枚举每种牌是按照1个一组,2个一组,3个一组还是4个一组出,再用错误解法1里面的贪心。
结果因为顺子剩下来的牌没有判断等原因又WA了两次才AC……

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int card[17],js[6],n,T,ans,lg;
int cal(){//贪心处理出牌方式
    int re=0,a=js[1],b=js[2],c=js[3],d=js[4],kl;
    kl=min(a/2,d),a-=kl*2,d-=kl,re+=kl;
    kl=min(b/2,d),b-=kl*2,d-=kl,re+=kl;
    kl=min(a,c),a-=kl,c-=kl,re+=kl;
    kl=min(b,c),b-=kl,c-=kl,re+=kl;
    return re+a+b+c+d;
}
void work(int x,int num){//搜索怎么拆牌
    if(x==14){ans=min(num+cal(),ans);return;}
    if(!card[x]){work(x+1,num);return;}
    if(card[x]==4){
        ++js[4];work(x+1,num);--js[4];
        ++js[3],++js[1];work(x+1,num);--js[3],--js[1];
        js[2]+=2;work(x+1,num);js[2]-=2;
        ++js[2],js[1]+=2;work(x+1,num);--js[2],js[1]-=2;
        js[1]+=4;work(x+1,num);js[1]-=4;
    }
    else if(card[x]==3){
        ++js[3];work(x+1,num);--js[3];
        ++js[1],++js[2];work(x+1,num);--js[1],--js[2];
        js[1]+=3;work(x+1,num);js[1]-=3;
    }
    else if(card[x]==2){
        ++js[2];work(x+1,num);--js[2];
        js[1]+=2;work(x+1,num);js[1]-=2;
    }
    else {++js[1];work(x+1,num);--js[1];}
}
void dfs(int x,int num){//搜索顺子
    if(num>=ans)return;
    if(x==14){work(1,num);return;}
    int i,cnt,j;
    for(i=x;i<=12;++i){
        cnt=0;
        for(j=i;j<=12;++j){
            if(!card[j])break;
            --card[j],++cnt;
            if(cnt>=5)dfs(x+1,num+1);
        }
        while(j>i)--j,++card[j];
    }
    for(i=x;i<=12;++i){
        cnt=0;
        for(j=i;j<=12;++j){
            if(card[j]<2)break;
            card[j]-=2,++cnt;
            if(cnt>=3)dfs(x+1,num+1);
        }
        while(j>i)--j,card[j]+=2;
    }
    for(i=x;i<=12;++i){
        cnt=0;
        for(j=i;j<=12;++j){
            if(card[j]<3)break;
            card[j]-=3,++cnt;
            if(cnt>=2)dfs(x+1,num+1);
        }
        while(j>i)--j,card[j]+=3;
    }
    dfs(x+1,num);
}
int main()
{
    freopen("lx.in","r",stdin);
    freopen("lx.out","w",stdout);
    int i,x,y;
    T=read(),n=read();
    while(T--){
        memset(card,0,sizeof(card));
        for(i=1;i<=n;++i){
            x=read(),y=read();
            if(x==1)++card[12];
            else if(x==2)++card[13];
            else if(!x)++card[0];
            else ++card[x-2];
        }
        ans=14;
        js[1]+=card[0],dfs(1,0);
        js[1]-=card[0];if(card[0]==2)dfs(1,1);
        printf("%d\n",ans);
    }
    return 0;
}
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *