题解

23 条题解

  • 3
    @ 2017-10-25 21:57:32

    有点坑,看起来很吓人,写起来还是比较好写的吧。
    注意三带一和四带二都可以带王

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    inline int read()
    {
        int x=0,f=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
        while(isdigit(c)){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    int T,n;
    int cnt[17],ans=99;
    const int size[4]={0,5,3,2};
    void dfs(int x)
    {
        if(x>ans) return;
        for(int i=3;i;i--)//处理顺子,i是顺子中相同牌的个数
        {
            int l=0;
            for(int j=3;j<=14;j++)
            {
                if(cnt[j]>=i) l++;else l=0;
                if(l>=size[i])
                {
                    for(int k=j-l+1;k<=j;k++) cnt[k]-=i;
                    dfs(x+1);
                    for(int k=j-l+1;k<=j;k++) cnt[k]+=i;
                }
            }
        }
        for(int i=2;i<=14;i++)//处理4带2,注意处理4带两对
        {
            if(cnt[i]>=4)
            {
                cnt[i]-=4;
                for(int j=2;j<=14;j++)
                {
                    if(i==j||cnt[j]<2) continue;
                    cnt[j]-=2;
                    for(int k=2;k<=14;k++) 
                    {
                        if(cnt[k]<2||k==j) continue;
                        cnt[k]-=2;dfs(x+1);cnt[k]+=2; 
                    }
                    cnt[j]+=2;
                }
                for(int j=2;j<=15;j++)
                {
                    if(i==j||cnt[j]<1) continue;
                    --cnt[j];
                    for(int k=2;k<=15;k++)
                    {
                        if(cnt[k]<1||k==j) continue;
                        --cnt[k];dfs(x+1);++cnt[k];
                    }
                    ++cnt[j];
                }
                cnt[i]+=4;
            }
        }
        for(int i=2;i<=14;i++)//处理3带(1\2)
        {
            if(cnt[i]>=3)//3带2
            {
                cnt[i]-=3;
                for(int j=2;j<=14;j++)
                {
                    if(cnt[j]<2||i==j) continue;
                    cnt[j]-=2;
                    dfs(x+1);
                    cnt[j]+=2;
                }
                for(int j=2;j<=15;j++)//3带1
                {
                    if(cnt[j]<1||i==j) continue;
                    --cnt[j];dfs(x+1);++cnt[j];
                }
                cnt[i]+=3;
            }
        }
        for(int i=2;i<=15;i++) if(cnt[i]>0) ++x;//剩下的牌只能每种相同的牌单独出,每种牌只用出一次
        ans=min(ans,x);
    }
    int main()
    {
        T=read(),n=read();
        while(T--)
        {
            memset(cnt,0,sizeof(cnt));
            ans=99;
            for(int i=1;i<=n;i++){int x=read();if(x!=0)cnt[x]++;else cnt[15]++;x=read();}
            cnt[14]=cnt[1];dfs(0);printf("%d\n",ans);   
        }
        return 0;
    }
    
    
  • 2
    @ 2016-11-18 08:07:07

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    int hand[5], ans;

    struct Card{
    int c[15], tep;
    void clear(){
    memset(c, 0, sizeof(c));
    tep = 0;
    }
    void print(){
    for(int i = 1; i <= 14; i++)
    cout<<c[i]<<" ";
    cout<<endl;
    }
    }start;

    int clac(Card now){
    int res = 0;
    memset(hand, 0, sizeof(hand));
    for(int i = 1; i <= 14; i++)
    hand[now.c[i]]++;
    if(now.c[14] == 2){
    if(hand[4] && hand[2] >= 2) hand[4]--, hand[2]-=2, res++;
    else if(hand[4] && hand[2]) hand[4]--, hand[2]--, res++;
    else hand[2]--, res++;
    }
    while(hand[4] && hand[1] >= 2) hand[4]--, hand[1]-=2, res++;
    while(hand[4] && hand[2] >= 2) hand[4]--, hand[2]-=2, res++;
    while(hand[4] && hand[2]) hand[4]--, hand[2]--, res++;
    while(hand[3] && hand[2]) hand[3]--, hand[2]--, res++;
    while(hand[3] && hand[1]) hand[3]--, hand[1]--, res++;
    res += hand[4] + hand[3] + hand[2] + hand[1];
    return res;
    }

    void dfs(Card now){
    int bri = now.tep + clac(now);
    ans = min(ans, bri);

    //单顺
    for(int i = 1; i <= 8; i++){
    int flag = 0;
    for(int j = i; j <= i+4; j++)
    if(!now.c[j]){
    flag = 1;
    break;
    }
    if(flag) continue;
    Card ne = now;
    ne.tep++;
    for(int j = i; j <= i+4; j++) ne.c[j]--; //5张
    dfs(ne);
    for(int j = i+5; j <= 12; j++){ //5+张
    if(ne.c[j]){
    ne.c[j]--;
    dfs(ne);
    }
    else
    break;
    }
    }

    //双顺
    for(int i = 1; i <= 10; i++){
    int flag = 0;
    for(int j = i; j <= i+2; j++)
    if(now.c[j] < 2){
    flag = 1;
    break;
    }
    if(flag) continue;
    Card ne = now;
    ne.tep++;
    for(int j = i; j <= i+2; j++)
    ne.c[j] -= 2;
    dfs(ne);
    for(int j = i+3; j <= 12; j++){
    if(ne.c[j] >= 2){
    ne.c[j] -= 2;
    dfs(ne);
    }
    else
    break;
    }
    }

    //三顺
    for(int i = 1; i <= 11; i++){
    int flag = 0;
    for(int j = i; j <= i+1; j++)
    if(now.c[j] < 3){
    flag = 1;
    break;
    }
    if(flag) continue;
    Card ne = now;
    ne.tep++;
    for(int j = i; j <= i+1; j++) ne.c[j] -= 3;
    dfs(ne);
    for(int j = i+2; j <= 12; j++){
    if(ne.c[j] >= 3){
    ne.c[j] -= 3;
    dfs(ne);
    }
    else
    break;
    }
    }
    }

    int main()
    {
    int T, n;
    scanf("%d%d", &T, &n);
    while(T--){
    start.clear();
    ans = n;
    for(int i = 1; i <= n; i++){
    int a, b;
    scanf("%d%d", &a, &b);
    if(a == 0) start.c[14]++;
    else if(a == 1) start.c[12]++;
    else if(a == 2) start.c[13]++;
    else start.c[a-2]++;
    }
    start.tep = 0;
    dfs(start);
    printf("%d\n", ans);
    }
    return 0;
    }
    搜索

  • 1
    @ 2017-08-27 19:25:49

    有人知道为什么会wa在95个点吗

    #include<bits/stdc++.h>
    #define cls(a,b) memset(a,b,sizeof(a))
    using namespace std;
    int B[5]={0,4,2,1};
    int cnt[110],sum[110],n,t,ans=0;
    int C() {
        #define RP(a,b,c,d) while(cnt[a]>=b&&cnt[c]>=d) cnt[a]-=b,cnt[c]-=d,res++
        cls(cnt,0);for(int i=1;i<=14;i++) cnt[sum[i]]++;int res=0;
        RP(4,1,2,2);RP(4,1,1,2);RP(3,1,2,1);RP(3,1,1,1);return res+cnt[1]+cnt[2]+cnt[3]+cnt[4];
    }
    void dfs(int S) {
        if(S>ans) return ;ans=min(ans,C()+S);int i,j,k,t,c;
        for(t=3;t>=1;t--) 
            for(i=3,j;i<=14;i++) {
                for(j=i;sum[j]>=t;j++);
                for(j--,k=i+B[t];k<=j;k++) {
                    for(c=i;c<=k;c++) sum[c]-=t;
                    dfs(S+1);
                    for(c=i;c<=k;c++) sum[c]+=t;
                }
            }
        if(sum[1]==2) sum[1]=0,dfs(S+1),sum[1]=2;
    }
    main() {
        cin>>t>>n;
        for(;t;t--) {
            cls(sum,0);ans=0;
            for(int i=1,a,b;i<=n;i++) {
                scanf("%d%d",&a,&b);
                if(a==1) a=14;else if(!a) a++;
                sum[a]++;
            }
            ans=C();dfs(0);cout<<ans<<"\n";
        }
    }
    
    
    • @ 2017-11-09 20:29:40

      双王不能当对子处理

  • 1
    @ 2016-08-11 11:45:17

    先预处理dp出打光i个4张码数相同的牌、j个3张码数相同的牌、k个2张码数相同的牌和l张单牌所需要的最少步数,再dfs顺子,结合预处理得出答案(PS:大小王要特判什么的,不能当对子用)

    评测结果
    测试数据 #0: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #1: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #2: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #3: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #4: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #5: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #6: Accepted, time = 15 ms, mem = 656 KiB, score = 1
    测试数据 #7: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #8: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #9: Accepted, time = 0 ms, mem = 664 KiB, score = 1
    测试数据 #10: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #11: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #12: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #13: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #14: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #15: Accepted, time = 0 ms, mem = 664 KiB, score = 1
    测试数据 #16: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #17: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #18: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #19: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #20: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #21: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #22: Accepted, time = 0 ms, mem = 664 KiB, score = 1
    测试数据 #23: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #24: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #25: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #26: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #27: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #28: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #29: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #30: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #31: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #32: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #33: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #34: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #35: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #36: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #37: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #38: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #39: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #40: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #41: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #42: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #43: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #44: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #45: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #46: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #47: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #48: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #49: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #50: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #51: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #52: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #53: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #54: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #55: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #56: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #57: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #58: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #59: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #60: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #61: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #62: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #63: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #64: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #65: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #66: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #67: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #68: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #69: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #70: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #71: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #72: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #73: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #74: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #75: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #76: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #77: Accepted, time = 15 ms, mem = 656 KiB, score = 1
    测试数据 #78: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #79: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #80: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #81: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #82: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #83: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #84: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #85: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #86: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #87: Accepted, time = 15 ms, mem = 656 KiB, score = 1
    测试数据 #88: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #89: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #90: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #91: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #92: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #93: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #94: Accepted, time = 0 ms, mem = 664 KiB, score = 1
    测试数据 #95: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #96: Accepted, time = 15 ms, mem = 660 KiB, score = 1
    测试数据 #97: Accepted, time = 0 ms, mem = 660 KiB, score = 1
    测试数据 #98: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    测试数据 #99: Accepted, time = 0 ms, mem = 656 KiB, score = 1
    Accepted, time = 240 ms, mem = 664 KiB, score = 100

    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iostream>
    int f[6][10][16][28],s[14],num[5],m,n,ans,temp;
    inline int read()
    {
        int c=getchar(),t=0;
        for(;c<48||57<c;c=getchar());
        do
        {
            t=(t<<3)+(t<<1)+c-48;
            c=getchar();
        }while(48<=c&&c<=57);
        return t;
    }
    inline int min(int x,int y) {x-=y;return y+(x&(x>>31));}
    inline void dfs(int x)
    {
        if(x>=ans) return;
        memset(num,0,sizeof(num));
        num[1]+=s[0];for(int i=1;i<=13;++i) ++num[s[i]];
        ans=min(ans,x+f[num[4]][num[3]][num[2]][num[1]]);
        for(int i=12,j;i>=5;--i)
        {
            for(j=i;j+3>=i&&s[j]>=1;--j) --s[j];
            if(j+3<i) for(;j&&s[j]>=1;--j) --s[j],dfs(x+1);
            for(int k=i;k>j;--k) ++s[k];
        }
        for(int i=12,j;i>=3;--i)
        {
            if(s[i]>=2&&s[i-1]>=2)
            {
                for(s[i]-=2,s[i-1]-=2,j=i-2;j&&s[j]>=2;--j) s[j]-=2,dfs(x+1);
                for(int k=i;k>j;--k) s[k]+=2;
            }
        }
        for(int i=12,j;i>=2;--i)
        {
            if(s[i]>=3)
            {
                for(s[i]-=3,j=i-1;j&&s[j]>=3;--j) s[j]-=3,dfs(x+1);
                for(int k=i;k>j;--k) s[k]+=3;
            }
        }
        if(s[0]==2) s[0]=0,dfs(x+1),s[0]=2;
    }
    int main()
    {
        m=read();n=read();
        memset(f,127,sizeof(f));
        f[0][0][0][0]=-1;
        for(int i=0;i<=5;++i)
        for(int j=0;j<=8;++j)
        for(int k=0;k<=13;++k)
        for(int l=0;l<=25;++l)
        {
            int &F=f[i][j][k][l];
            if(i>=1&&k>=2) F=min(F,f[i-1][j][k-2][l]);
            if(i>=1&&l>=2) F=min(F,f[i-1][j][k][l-2]);
            if(i>=1) F=min(F,f[i-1][j][k][l]);
            if(j>=1&&k>=1) F=min(F,f[i][j-1][k-1][l]);
            if(j>=1&&l>=1) F=min(F,f[i][j-1][k][l-1]);
            if(j>=1) F=min(F,f[i][j-1][k][l]);
            if(k>=1) F=min(F,f[i][j][k-1][l]);
            if(l>=1) F=min(F,f[i][j][k][l-1]);
            ++F;
            if(i>=1) F=min(F,min(f[i-1][j+1][k][l+1],f[i-1][j][k+2][l]));
            if(j>=1) F=min(F,f[i][j-1][k+1][l+1]);
            if(k>=1) F=min(F,f[i][j][k-1][l+2]);
        }
        while(m--)
        {
            memset(s,0,sizeof(s));ans=23;
            for(int i=1;i<=n;++i,read())
            {
                temp=read();
                if(temp==0) ++s[0];
                else ++s[(temp+10)%13+1];
            }
            dfs(0);
            printf("%d\n",ans);
        }
    }```
    
  • 0
    @ 2017-11-06 20:15:39

    dp[i][j][k][l][m]表示不考虑顺子的情况下,(数码相同的牌有四张的有i种【emmm也就是不算王炸的纯炸弹有x个】,以此类推,有三张的有j种,两张的有k种,一张的有l种,特别的,王的数量为m个)的情况,最少能够出完牌的次数。
    王之所以分开考虑是因为王炸不能算对子,四带两对和三带一对的情况对于王炸要分开考虑,与其特判不如直接新开一维记录
    先预处理出能够用得到的dp数组的值,然后dfs枚举顺子
    本来dp数组中没有考虑拆牌的情况,只有十多行的状态转移,洛谷上面的原版斗地主能够a掉,但是洛谷的斗地主加强版和vijos的斗地主都不行
    于是狠心把所有能够考虑到的拆牌的情况都写了进去,令人窒息的五十行if......
    其实有的拆牌情况可以不用考虑的,只是我当时实在是不想思考了......
    幸好一遍过,没有怎么调试,否则我会疯的......

     #include <stdio.h>
    #include <algorithm>
    #include <string.h>
    #define MAX4 7
    #define MAX3 9
    #define MAX2 14
    #define MAX1 25
    #define MAX0 2
    using namespace std;
    int T,n;
    int card[30];
    int dp[8][10][15][26][3];
    int finalans;
    inline int read()
    {
        int k=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}
        return k*f;
    }
    inline void DpBuild()
    {
        for(int i=0;i<=MAX4;i++)
        {
            for(int j=0;j<=MAX3;j++)
            {
                for(int k=0;k<=MAX2;k++)
                {
                    for(int l=0;l<=MAX1;l++)
                    {
                        for(int m=0;m<=MAX0;m++)
                        {
                            dp[i][j][k][l][m]=i+j+k+l+(m==0?0:1);
                        }
                    }
                }
            }
        }
        for(int i=0;i<=MAX4;i++)
        {
            int usingj=(MAX1-4*i)/3+1;
            for(int j=0;j<=usingj;j++)
            {
                int usingk=(MAX1-4*i-3*j)/2+1;
                for(int k=0;k<=usingk;k++)
                {
                    int usingl=(MAX1-4*i-3*j-2*k)+1;
                    for(int l=0;l<=usingl;l++)
                    {
                        for(int m=0;m<=MAX0;m++)
                        {
                            if(m>1) dp[i][j][k][l][m]=min(dp[i][j][k][l][m-2]+1,dp[i][j][k][l][m]);
                            if(m>0) dp[i][j][k][l][m]=min(dp[i][j][k][l][m-1]+1,dp[i][j][k][l][m]);
                            if(i>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l][m]+1,dp[i][j][k][l][m]);
                            if(l>0) dp[i][j][k][l][m]=min(dp[i][j][k][l-1][m]+1,dp[i][j][k][l][m]);
                            if(k>0) dp[i][j][k][l][m]=min(dp[i][j][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(j>0) dp[i][j][k][l][m]=min(dp[i][j-1][k+1][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0) dp[i][j][k][l][m]=min(dp[i-1][j+1][k][l][m]+1,dp[i][j][k][l][m]);
                            if(k>0) dp[i][j][k][l][m]=min(dp[i][j][k-1][l][m]+1,dp[i][j][k][l][m]);
                            if(j>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>0) dp[i][j][k][l][m]=min(dp[i+1][j][k-1][l][m]+1,dp[i][j][k][l][m]);
                            if(j>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l+1][m]+1,dp[i][j][k][l][m]);
                            if(j>0&&m>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l][m-1]+1,dp[i][j][k][l][m]);
                            if(j>0&&l>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l-1][m]+1,dp[i][j][k][l][m]);
                            if(j>0&&k>0) dp[i][j][k][l][m]=min(dp[i][j-1][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(j>1) dp[i][j][k][l][m]=min(dp[i][j-2][k+1][l][m]+1,dp[i][j][k][l][m]);
                            if(j>0&&i>0) dp[i][j][k][l][m]=min(dp[i-1][j-1+1][k][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&l>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l-1+1][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l+2][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>1) dp[i][j][k][l][m]=min(dp[i-2][j+1][k][l+1][m]+1,dp[i][j][k][l][m]); 
                            if(i>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l+1][m-1]+1,dp[i][j][k][l][m]);
                            if(j>0&&k>0) dp[i][j][k][l][m]=min(dp[i][j-1][k-1][l][m]+1,dp[i][j][k][l][m]);
                            if(j>1) dp[i][j][k][l][m]=min(dp[i][j-2][k][l+1][m]+1,dp[i][j][k][l][m]);
                            if(j>0&&i>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k][l+2][m]+1,dp[i][j][k][l][m]);
                            if(i>1) dp[i][j][k][l][m]=min(dp[i-2][j][k+1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&l>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l-1+1][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&l>0&&j>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l-1][m]+1,dp[i][j][k][l][m]);
                            if(i>1&&l>0) dp[i][j][k][l][m]=min(dp[i-2][j+1][k][l-1][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&m>1) dp[i][j][k][l][m]=min(dp[i-1][j][k][l][m-2]+1,dp[i][j][k][l][m]);
                            if(i>0&&k>1) dp[i][j][k][l][m]=min(dp[i-1][j][k-2][l+2][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k-1+1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>1&&k>0) dp[i][j][k][l][m]=min(dp[i-2][j+1][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>1) dp[i][j][k][l][m]=min(dp[i-1][j-2][k+2][l][m]+1,dp[i][j][k][l][m]);
                            if(i>1&&j>0) dp[i][j][k][l][m]=min(dp[i-2][j-1+1][k+1][l][m]+1,dp[i][j][k][l][m]);
                            if(i>2) dp[i][j][k][l][m]=min(dp[i-3][j+2][k][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&k>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l+1][m-1]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l][m-1]+1,dp[i][j][k][l][m]);
                            if(i>1&&m>0) dp[i][j][k][l][m]=min(dp[i-2][j+1][k][l][m-1]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>1&&k>0) dp[i][j][k][l][m]=min(dp[i-2][j][k-1+1][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&j>1) dp[i][j][k][l][m]=min(dp[i-1][j-2][k][l+2][m]+1,dp[i][j][k][l][m]);
                            if(i>1&&j>0) dp[i][j][k][l][m]=min(dp[i-2][j-1][k+1][l+1][m]+1,dp[i][j][k][l][m]);
                            if(i>2) dp[i][j][k][l][m]=min(dp[i-3][j][k+2][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&k>1) dp[i][j][k][l][m]=min(dp[i-1][j][k-2][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&l>1) dp[i][j][k][l][m]=min(dp[i-1][j][k][l-2][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l][m]+1,dp[i][j][k][l][m]);
                            if(i>1) dp[i][j][k][l][m]=min(dp[i-2][j][k][l][m]+1,dp[i][j][k][l][m]);
                            if(i>0&&l>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l-1][m-1]+1,dp[i][j][k][l][m]);
                            //printf("dp[%d][%d][%d][%d][%d]=%d\n",i,j,k,l,m,dp[i][j][k][l][m]);
                        }
                    }
                }
            }
        }   
    }
    void Search(int now)
    {
        for(int i=3;i<=13;i++)
        {
            if(card[i]>=3&&card[i+1]>=3)
            {
                card[i]-=3;card[i+1]-=3;
                Search(now+1);
                int j=i+2;
                while(j<=14&&card[j]>=3)
                {
                    card[j]-=3;
                    Search(now+1);
                    j++;
                }
                for(int k=i;k<j;k++)
                {
                    card[k]+=3;
                }
            }
        }
        for(int i=3;i<=12;i++)
        {
            if(card[i]>=2&&card[i+1]>=2&&card[i+2]>=2)
            {
                card[i]-=2;card[i+1]-=2;card[i+2]-=2;
                Search(now+1);
                int j=i+3;
                while(j<=14&&card[j]>=2)
                {
                    card[j]-=2;
                    Search(now+1);
                    j++;
                }
                for(int k=i;k<j;k++)
                {
                    card[k]+=2;
                }
            }
        }
        for(int i=3;i<=10;i++)
        {
            if(card[i]>0&&card[i+1]>0&&card[i+2]>0&&card[i+3]>0&&card[i+4]>0)
            {
                card[i]--;card[i+1]--;card[i+2]--;card[i+3]--;card[i+4]--;
                Search(now+1);
                int j=i+5;
                while(j<=14&&card[j]>0)
                {
                    card[j]--;
                    Search(now+1);
                    j++;
                }
                for(int k=i;k<j;k++)
                {
                    card[k]++;
                }
            }
        }
        int num4=0,num3=0,num2=0,num1=0,joker=0;
        for(int i=3;i<=15;i++)
        {
            if(card[i]==4) num4++;
            else if(card[i]==3) num3++;
            else if(card[i]==2) num2++;
            else if(card[i]==1) num1++;
        }
        joker=card[16];
        finalans=min(finalans,dp[num4][num3][num2][num1][joker]+now);
        //printf("%d %d %d %d %d %d %d\n",num4,num3,num2,num1,joker,dp[num4][num3][num2][num1][joker]+now,finalans);
    }
    int main()
    {
        //freopen("landlords.in","r",stdin);
        //freopen("landlords.out","w",stdout);
        int x,y;
        T=read();n=read();
        DpBuild();
        while(T--)
        {
            finalans=n;
            memset(card,0,sizeof(card));
            for(int i=1;i<=n;i++)
            {
                x=read();y=read();
                if(x>=3&&x<=13) card[x]++;
                else if(x>=1&&x<=2) card[x+13]++;
                else if(x==0) card[16]++;
            }
            int num4=0,num3=0,num2=0,num1=0,joker=0;
            for(int i=3;i<=15;i++)
            {
                if(card[i]==4) num4++;
                else if(card[i]==3) num3++;
                else if(card[i]==2) num2++;
                else if(card[i]==1) num1++;
            }
            joker=card[16];
            finalans=min(finalans,dp[num4][num3][num2][num1][joker]);
            Search(0);
            printf("%d\n",finalans);
        }
        return 0;
    }
    
    
    
    
  • 0
    @ 2017-10-21 20:00:51

    纯暴力。。。500行。。。简直爆炸。。。

    #include <iostream>
    using namespace std;
    #define For(i, j, k) for(int i = j; i <= k; i++)
    int pa[100];
    int T;
    int n;
    int ans = 999999999;
    int t;
    int fi(){
        For(i, 0, 13){
            if (pa[i] != 0){
                return i;
            }
        }
        return 98765;
    }
    
    void s(){
        if (t > ans){
            return;
        }
        int po = fi();
    
        if (po == 98765){
            ans = min(ans, t);
            return;
        }
    
        if (po == 0){
            if (pa[po] >= 2){
    
                pa[po] -= 2;
                t ++;
                s();
                t --;
                pa[po] += 2;
            }
            if (pa[po] >= 1) {
    
                pa[po] -= 1;
                t ++;
                s();
                t --;
                pa[po] += 1;
    
    
                For(j, po + 1, 13){
                    if (pa[j] >= 3){
                        pa[j] -= 3;
                        pa[po] --;
                        t ++;
                        s();
                        t --;
                        pa[po] ++;
                        pa[j] += 3;
                    }
                }
    
                For(j, po + 1, 13){
                    if (pa[j] >= 4){
                        For(k, po + 1, 13){
                            if (k != j && pa[k] >= 1){
                                pa[j] -= 4;
                                pa[po] --;
                                pa[k] --;
                                t ++;
                                s();
                                t --;
                                pa[k] ++;
                                pa[po] ++;
                                pa[j] += 4;
                            }
                        }
                    }
                }
            }
    
        }
    
        if (po == 1){
            if (pa[po] >= 4){
                pa[po] -= 4;
                t ++;
                s();
                t --;
                pa[po] += 4;
    
                For(i, po + 1, 13){
                    For(j, i + 1, 13){
                        if (pa[i] >= 1 && pa[j] >= 1){
                            pa[i] -= 1;
                            pa[j] -= 1;
                            pa[po] -= 4;
                            t ++;
                            s();
                            t --;
                            pa[po] += 4;
                            pa[i] += 1;
                            pa[j] += 1;
                        }
    
                    }
                }
    
    
                For(i, po + 1, 13){
                    For(j, i + 1, 13){
                        if (pa[i] >= 2 && pa[j] >= 2){
                            pa[i] -= 2;
                            pa[j] -= 2;
                            pa[po] -= 4;
                            t ++;
                            s();
                            t --;
                            pa[po] += 4;
                            pa[i] += 2;
                            pa[j] += 2;
                        }
    
                    }
                }
            }
            if (pa[po] >= 3){
                pa[po] -= 3;
                t ++;
                s();
                t --;
                pa[po] += 3;
    
                For(i, po + 1, 13){
                    if (pa[i] >= 1){
                        pa[po] -= 3;
                        pa[i] --;
                        t ++;
                        s();
                        t --;
                        pa[po] += 3;
                        pa[i] ++;
                    }
                }
    
                For(i, po + 1, 13){
                    if (pa[i] >= 2){
                        pa[po] -= 3;
                        pa[i] -= 2;
                        t ++;
                        s();
                        t --;
                        pa[po] += 3;
                        pa[i] += 2;
                    }
                }
    
    
    
            }
            if (pa[po] >= 2){
                pa[po] -= 2;
                t ++;
                s();
                t --;
                pa[po] += 2;
    
    
                For(j, po + 1, 13){
                    if (pa[j] >= 4){
    
                        For(k, po + 1, 13){
                            if (k != j && pa[k] >= 2){
    
                                pa[j] -= 4;
                                pa[po] -= 2;
                                pa[k] -= 2;
                                t ++;
                                s();
                                t --;
                                pa[k] += 2;
                                pa[po] += 2;
                                pa[j] += 4;
                            }
    
    
                        }
    
                    }
                }
    
    
                For(j, po + 1, 13){
                    if (pa[j] >= 3){
                        pa[j] -= 3;
                        pa[po] -= 2;
                        t ++;
                        s();
                        t --;
                        pa[po] += 2;
                        pa[j] += 3;
                    }
                }
    
            }
            if (pa[po] >= 1){
    
                For(j, po + 1, 13){
                    if (pa[j] >= 3){
                        pa[j] -= 3;
                        pa[po] --;
                        t ++;
                        s();
                        t --;
                        pa[po] ++;
                        pa[j] += 3;
                    }
                }
    
                pa[po] -= 1;
                t ++;
                s();
                t --;
                pa[po] += 1;
    
                For(j, po + 1, 13){
                    if (pa[j] >= 4){
    
                        For(k, po + 1, 13){
                            if (k != j && pa[k] >= 1){
    
                                pa[j] -= 4;
                                pa[po] --;
                                pa[k] --;
                                t ++;
                                s();
                                t --;
                                pa[k] ++;
                                pa[po] ++;
                                pa[j] += 4;
                            }
    
    
                        }
    
                    }
                }
    
            }
    
    
    
        }
        if (po >= 2){
            if (pa[po] >= 4){
                pa[po] -= 4;
                t ++;
                s();
                t --;
                pa[po] += 4;
    
                For(i, po + 1, 13){
                    For(j, i + 1, 13){
                        if (pa[i] >= 1 && pa[j] >= 1){
                            pa[i] -= 1;
                            pa[j] -= 1;
                            pa[po] -= 4;
                            t ++;
                            s();
                            t --;
                            pa[po] += 4;
                            pa[i] += 1;
                            pa[j] += 1;
                        }
    
                    }
                }
    
    
                For(i, po + 1, 13){
                    For(j, i + 1, 13){
                        if (pa[i] >= 2 && pa[j] >= 2){
                            pa[i] -= 2;
                            pa[j] -= 2;
                            pa[po] -= 4;
                            t ++;
                            s();
                            t --;
                            pa[po] += 4;
                            pa[i] += 2;
                            pa[j] += 2;
                        }
    
                    }
                }
            }
            if (pa[po] >= 3){
                pa[po] -= 3;
                t ++;
                s();
                t --;
                pa[po] += 3;
    
                For(i, po + 1, 13){
                    if (pa[i] >= 1){
                        pa[po] -= 3;
                        pa[i] --;
                        t ++;
                        s();
                        t --;
                        pa[po] += 3;
                        pa[i] ++;
                    }
                }
    
                For(i, po + 1, 13){
                    if (pa[i] >= 2){
                        pa[po] -= 3;
                        pa[i] -= 2;
                        t ++;
                        s();
                        t --;
                        pa[po] += 3;
                        pa[i] += 2;
                    }
                }
    
                For(j, po + 1, 13){
                    if (pa[j] <= 2){
                        break;
                    }
                    if (j - po + 1 >= 2){
                        For(k, po, j){
                            pa[k] -= 3;
                        }
                        t++;
                        s();
                        t--;
                        For(k, po, j){
                            pa[k] += 3;
                        }
                    }
                }
            }
            if (pa[po] >= 2){
                pa[po] -= 2;
                t ++;
                s();
                t --;
                pa[po] += 2;
    
                For(j, po + 1, 13){
                    if (pa[j] <= 1){
                        break;
                    }
                    if (j - po + 1 >= 3){
                        For(k, po, j){
                            pa[k] -= 2;
                        }
                        t++;
                        s();
                        t--;
                        For(k, po, j){
                            pa[k] += 2;
                        }
                    }
                }
    
    
                For(j, po + 1, 13){
                    if (pa[j] >= 4){
    
                        For(k, po + 1, 13){
                            if (k != j && pa[k] >= 2){
    
                                pa[j] -= 4;
                                pa[po] -= 2;
                                pa[k] -= 2;
                                t ++;
                                s();
                                t --;
                                pa[k] += 2;
                                pa[po] += 2;
                                pa[j] += 4;
                            }
    
    
                        }
    
                    }
                }
    
    
                For(j, po + 1, 13){
                    if (pa[j] >= 3){
                        pa[j] -= 3;
                        pa[po] -= 2;
                        t ++;
                        s();
                        t --;
                        pa[po] += 2;
                        pa[j] += 3;
                    }
                }
    
            }
            if (pa[po] >= 1){
                pa[po] -= 1;
                t ++;
                s();
                t --;
                pa[po] += 1;
    
                For(j, po + 1, 13){
                    if (pa[j] >= 3){
                        pa[j] -= 3;
                        pa[po] --;
                        t ++;
                        s();
                        t --;
                        pa[po] ++;
                        pa[j] += 3;
                    }
                }
    
                For(j, po + 1, 13){
                    if (pa[j] >= 4){
    
                        For(k, po + 1, 13){
                            if (k != j && pa[k] >= 1){
    
                                pa[j] -= 4;
                                pa[po] --;
                                pa[k] --;
                                t ++;
                                s();
                                t --;
                                pa[k] ++;
                                pa[po] ++;
                                pa[j] += 4;
                            }
    
    
                        }
    
                    }
                }
    
                For(j, po + 1, 13){
                    if (pa[j] == 0){
                        break;
                    }
                    if (j - po + 1 >= 5){
                        For(k, po, j){
                            pa[k] --;
                        }
                        t++;
                        s();
                        t--;
                        For(k, po, j){
                            pa[k] ++;
                        }}
                }
            }
        }
    
    
    }
    int main(){
    //  freopen("landlords.in", "r", stdin);
    //  freopen("landlords.out", "w", stdout);
        cin >> T >> n;
    
        For(dhias, 1, T){
            For(i, 0, 99){
                pa[i] = 0;
            }
            t = 0;
            ans = 999999999;
            int tjo, tch;
            For(i, 1, n){
                cin >> tjo >> tch;
                if (3 <= tjo && tjo <= 13){
                    pa[tjo - 1]++;
                }
                if (tjo == 0){
                    pa[0] ++;
                }
                if (tjo == 1){
                    pa[13] ++;
                }
                if (tjo == 2){
                    pa[1] ++;
                }
            }
            s();
            cout << ans << endl;
        }
        return 0;
    }
    
  • 0
    @ 2017-10-20 13:25:04

    先预处理不打顺子的情况:记下有c1种1张的数码,c2种2张的数码,c3种3张的数码,c4种4张的数码时打光所有牌需要的最小次数。然后DFS搜索已经打过顺子的所有可能情况。
    最坑爹的是俩王不能被带...还要加个特判。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int f[24][13][9][7];
    int dfs(int c1,int c2,int c3,int c4)
    {
        if(f[c1][c2][c3][c4]>-1)   return f[c1][c2][c3][c4];
        if(!(c1||c2||c3||c4))   return f[c1][c2][c3][c4]=0;
        int ans=1e9;
        if(c4>0)
        {
            if(c2>1)   ans=min(ans,dfs(c1,c2-2,c3,c4-1));
            if(c1>1)   ans=min(ans,dfs(c1-2,c2,c3,c4-1));
            ans=min(ans,dfs(c1,c2,c3,c4-1));
        }
        if(c3>0)
        {
            if(c2>0)   ans=min(ans,dfs(c1,c2-1,c3-1,c4));
            if(c1>0)   ans=min(ans,dfs(c1-1,c2,c3-1,c4));
            ans=min(ans,dfs(c1,c2,c3-1,c4));
        }
        if(c2>0)   ans=min(ans,dfs(c1,c2-1,c3,c4));
        if(c1>0)   ans=min(ans,dfs(c1-1,c2,c3,c4));
        return f[c1][c2][c3][c4]=ans+1;
    }
    int DFS(int A[])
    {
        int C[5]; //有i张的有几个
        bool B[15][5]; //i号牌是否有j张
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));//init.
        for(int i=0;i<=13;i++)
            for(int j=1;j<=A[i];j++)
            {
                B[i][j]=1;//i号牌有j张
                if(i==1)   B[14][j]=1;//A放到K后面
            }
        for(int i=0;i<=13;i++)   C[A[i]]++;//1234张的号码的数量
        int ans=dfs(C[1],C[2],C[3],C[4]); //不考虑顺子
        int last=0,shunzi[4]={0,5,3,2};//顺子起始,顺子张数
        for(int j=3;j>0;j--)//123连顺
        {
            last=0;
            for(int i=3;i<=14;i++)//搜3~A(14)
            {
                if(B[i][j]&&(last==0))   last=i;//i号有j张,则记录顺子起始
                if(B[i][j]&&last>0&&((i-last+1)>=shunzi[j])) 
                  //顺子已有shunzi[j]张以上
                {
                    int tA[14];
                    for(int t=0;i-last-t+1>=shunzi[j];t++)
                    {
                        for(int k=0;k<=13;k++)   tA[k]=A[k];
                        for(int k=last+t;k<=i;k++)
                        {
                            if(k==14)   tA[1]=A[1]-j;
                            else   tA[k]=A[k]-j;
                        }//新的方案
                        ans=min(ans,1+DFS(tA));
                    }
                }
                if(!B[i][j])   last=0;//要断
            }
        }
        return ans;
    }
    int main()
    {
        int x,n;
        scanf("%d%d",&x,&n);
        memset(f,-1,sizeof(f));
        for(int c1=0;c1<=23;c1++)
           for(int c2=0;c2<=12;c2++)
              for(int c3=0;c3<=8;c3++)
                 for(int c4=0;c4<=6;c4++)
                     dfs(c1,c2,c3,c4);
        //初始化:对于每一种张数的号码的数量,不打顺子的最小值
        while(x--)
        {
            int A[14],anti_kengdie=0;//i点的张数
            memset(A,0,sizeof(A));
            for(int i=1;i<=n;i++)
            {
                int num,d;
                scanf("%d%d",&num,&d);
                A[num]++;//num点的牌共几张
            }
            if(A[0]==2)
            {
                A[0]=0;
                anti_kengdie=1;
            }
            printf("%d\n",anti_kengdie+DFS(A));
        }
        return 0;
    }
    
  • 0
    @ 2017-10-20 07:28:39

    先初始化不打顺子的情形,f[c1][c2][c3][c4]表示ci点的牌有i张时,打完需要的最少次数
    之后dfs搜索打完若干顺子后的所有可能情况。
    注意俩猫不能被三、四带走...坑爹呢这是
    cpp
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int f[24][13][9][7];
    int dfs(int c1,int c2,int c3,int c4)
    {
    if(f[c1][c2][c3][c4]>-1) return f[c1][c2][c3][c4];
    if(!(c1||c2||c3||c4)) return f[c1][c2][c3][c4]=0;
    int ans=1e9;
    if(c4>0)
    {
    if(c2>1) ans=min(ans,dfs(c1,c2-2,c3,c4-1));
    if(c1>1) ans=min(ans,dfs(c1-2,c2,c3,c4-1));
    ans=min(ans,dfs(c1,c2,c3,c4-1));
    }
    if(c3>0)
    {
    if(c2>0) ans=min(ans,dfs(c1,c2-1,c3-1,c4));
    if(c1>0) ans=min(ans,dfs(c1-1,c2,c3-1,c4));
    ans=min(ans,dfs(c1,c2,c3-1,c4));
    }
    if(c2>0) ans=min(ans,dfs(c1,c2-1,c3,c4));
    if(c1>0) ans=min(ans,dfs(c1-1,c2,c3,c4));
    return f[c1][c2][c3][c4]=ans+1;
    }
    int DFS(int A[])
    {
    int C[5]; //有i张的有几个
    bool B[15][5]; //i号牌是否有j张
    memset(B,0,sizeof(B));
    memset(C,0,sizeof(C));//init.
    for(int i=0;i<=13;i++)
    for(int j=1;j<=A[i];j++)
    {
    B[i][j]=1;//i号牌有j张
    if(i==1) B[14][j]=1;//A放到K后面
    }
    for(int i=0;i<=13;i++) C[A[i]]++;//1234张的号码的数量
    int ans=dfs(C[1],C[2],C[3],C[4]); //不考虑顺子
    int last=0,shunzi[4]={0,5,3,2};//顺子起始,顺子张数
    for(int j=3;j>0;j--)//123连顺
    {
    last=0;
    for(int i=3;i<=14;i++)//搜3~A(14)
    {
    if(B[i][j]&&(last==0)) last=i;//i号有j张,则记录顺子起始
    if(B[i][j]&&last>0&&((i-last+1)>=shunzi[j])) //顺子已有shunzi[j]张以上
    {
    int tA[14];
    for(int t=0;i-last-t+1>=shunzi[j];t++)
    {
    for(int k=0;k<=13;k++) tA[k]=A[k];
    for(int k=last+t;k<=i;k++)
    {
    if(k==14) tA[1]=A[1]-j;
    else tA[k]=A[k]-j;
    }//新的方案
    ans=min(ans,1+DFS(tA));
    }
    }
    if(!B[i][j]) last=0;//顺子断
    }
    }
    return ans;
    }
    int main()
    {
    int x,n;
    scanf("%d%d",&x,&n);
    memset(f,-1,sizeof(f));
    for(int c1=0;c1<=23;c1++)
    for(int c2=0;c2<=12;c2++)
    for(int c3=0;c3<=8;c3++)
    for(int c4=0;c4<=6;c4++)
    dfs(c1,c2,c3,c4);
    //初始化:对于每一种张数的牌的数量,不打顺子出完的最小次数
    while(x--)
    {
    int A[14],anti_kengdie=0;//i点的张数 及 防止俩猫不能带的坑爹
    memset(A,0,sizeof(A));
    for(int i=1;i<=n;i++)
    {
    int num,d;
    scanf("%d%d",&num,&d);
    A[num]++;//num点的牌共几张
    }
    if(A[0]==2)
    {
    A[0]=0;
    anti_kengdie=1;
    }
    printf("%d\n",anti_kengdie+DFS(A));
    }
    return 0;
    }

  • 0
    @ 2017-07-26 21:24:52

    对于这题,我对于出了这100个数据的大佬只能说是佩服透了、跪烂了!
    话说我在99分那里死了很久,然后发现网上好多的所谓的AC代码也是99的~
    无语无语
    然后看了楼下的一位大佬,才发现一个东西:
    #王炸#
    🚀火箭🚀是不能放在三带二里面的,不过题目好像没说……(可能是我没看见)
    其实我还是觉得奇怪:比如现在只剩下3组炸弹了,照大多数标算的(包括我的),这样要3次,
    but其实来2次4带2就可以解决……不知道是否有人能给我答案(期待)
    这题是这样做的:
    1. 对于顺子,dfs 按照3顺子、2顺子、1顺子顺序来(可能会快一点)
    2. 对于每种剩余的牌的情况,不管还能不能打出顺子,我们统计一下剩余的不打顺子最少几个,是可以不通过搜索直接解决的(但我还是不大理解),用这个答案来更新结果;
    3. 剪枝: if (now>=ans) return;

    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    const int P=20;
    // Three are totally 14 kinds of cards :0~13 
    int p[P],T,n,ans;
    int restep(){
        int c[5],step=0/*,s1,s2*/;
        memset(c,0,sizeof c);
        for (int i=0;i<=13;i++)
            c[p[i]]++;
        if (p[0]==2){
            if (c[4]>=1&&c[2]>=2)
                c[4]-=1,c[2]-=2,step++;
            else if (c[4]>=1&&c[2]>=1)
                c[4]-=1,c[2]-=1,step++;
            else
                c[2]-=1,step++;
        }
        while (c[4]>=1&&c[1]>=2)c[4]-=1,c[1]-=2,step++;
        while (c[4]>=1&&c[2]>=2)c[4]-=1,c[2]-=2,step++;
        while (c[4]>=1&&c[2]>=1)c[4]-=1,c[2]-=1,step++;
        while (c[3]>=1&&c[2]>=1)c[3]-=1,c[2]-=1,step++;
        while (c[3]>=1&&c[1]>=1)c[3]-=1,c[1]-=1,step++;
        return step+c[1]+c[2]+c[3]+c[4];
    }
    void dfs(int now){
        int le,ri,L=2,R=14;
        if (now>=ans)
            return;
        int step=restep();
        if (ans>now+step)
            ans=now+step;
        //三顺子 
        for (le=L;le<R;le++){
            ri=le;
            while (ri<R&&p[ri]>=3)
                ri++;
            if (ri-le>=2)
                for (int x=le+2;x<=ri;x++){
                    for (int i=le;i<x;i++)
                        p[i]-=3;
                    dfs(now+1);
                    for (int i=le;i<x;i++)
                        p[i]+=3;
                }
        }
        //三顺子 
        //双顺子 
        for (le=L;le<R;le++){
            ri=le;
            while (ri<R&&p[ri]>=2)
                ri++;
            if (ri-le>=3)
                for (int x=le+3;x<=ri;x++){
                    for (int i=le;i<x;i++)
                        p[i]-=2;
                    dfs(now+1);
                    for (int i=le;i<x;i++)
                        p[i]+=2;
                }
        }
        //双顺子 
        //单顺子 
        for (le=L;le<R;le++){
            ri=le;
            while (ri<R&&p[ri]>=1)
                ri++;
            if (ri-le>=5)
                for (int x=le+5;x<=ri;x++){
                    for (int i=le;i<x;i++)
                        p[i]-=1;
                    dfs(now+1);
                    for (int i=le;i<x;i++)
                        p[i]+=1;
                }
        }
        //单顺子 
    }
    int main(){
        scanf("%d%d",&T,&n);
        while (T--){
            memset(p,0,sizeof p);
            for (int i=1,a,b;i<=n;i++){
                scanf("%d%d",&a,&b);
                if (a==1)
                    a=13;
                else if (a>0)
                    a--;
                p[a]++;
            }
            ans=n;
            dfs(0);
            printf("%d\n",ans);
        }
        return 0;
    }
    
    • @ 2017-08-16 12:40:54

      三个炸弹不可以两次四带二,因为必须是两张不同的单牌或两对不同的对子

  • 0
    @ 2016-10-17 15:45:52

    搜顺子,然后计算对子和带牌
    ```c++

    #include<iostream>
    #include<cstdio>
    #include<cctype>
    #include<cstring>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #define smin(a, b) a = min(a, b)
    using namespace std;
    typedef bool boolean;
    template<typename T>
    inline void readInteger(T& u){
    char x;
    while(!isdigit((x = getchar())));
    for(u = x - '0'; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - '0');
    ungetc(x, stdin);
    }

    int n;
    int kase;
    int key[14] = {0, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int had[16];

    inline void init(){
    memset(had, 0, sizeof(had));
    for(int i = 1, a, b; i <= n; i++){
    readInteger(a);
    readInteger(b);
    if(a == 0) had[13 + b]++;
    else had[key[a]]++;
    }
    }

    int calc(){
    int counter[5] = {0, 0, 0, 0, 0};
    for(int i = 1; i <= 15; i++){
    if(had[i] > 0){
    counter[had[i]]++;
    }
    }
    int reter = 0;
    boolean aFlag = 0;
    if(had[14] == 1 && had[15] == 1){

    aFlag = 1;
    }
    while(counter[4] && counter[2] >= 2) reter++, counter[4] -= 1, counter[2] -= 2;
    while(counter[4] && counter[1] >= 2) reter++, counter[4] -= 1, counter[1] -= 2;
    while(counter[4] && counter[2]) reter++, counter[4] -= 1, counter[2] -= 1;
    while(counter[3] && counter[2]) reter++, counter[3] -= 1, counter[2] -= 1;
    while(counter[3] && counter[1]) reter++, counter[3] -= 1, counter[1] -= 1;
    if(counter[1] >= 2 && aFlag) counter[1] -= 1;
    return reter + counter[1] + counter[2] + counter[3] + counter[4];
    }

    int result;
    void search(int last, int times){
    if(last == 0){
    smin(result, times);
    return;
    }
    smin(result, times + calc());
    if(times >= result) return;
    //顺子
    if(last >= 5){
    for(int p = 3; p >= 1; p--){
    for(int i = 1; i <= 12; i++){
    int k = i;
    while(had[k] >= p && k < 13) k++;
    if((k - i) * p >= 5){
    for(int j = i; j < k; j++){
    had[j] -= p;
    }
    for(int j = k - 1; j >= i; j--){
    if((j - i + 1) * p >= 5)
    search(last - (j - i + 1) * p, times + 1);
    had[j] += p;
    }
    }

    }
    }
    }
    }

    int main(){
    readInteger(kase);
    readInteger(n);
    while(kase--){
    init();
    result = n;
    search(n, 0);
    printf("%d\n", result);
    }
    return 0;
    }
    ```

  • 0
    @ 2016-10-10 21:42:48

    在ccz大爷的帮助下终于知道了ta[]tb[]会改变。。。见识了大爷的各种神乎其神的调试技巧。。。跪烂了跪烂了。。。
    然后这份暴力+剪枝的代码vijos上96.官方数据95.嗯其他的都是WA不想理了TAT

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cctype>
    #include<algorithm>
    using namespace std;
    #define rep(i,s,t) for(int i=s;i<=t;i++)
    #define dwn(i,s,t) for(int i=s;i>=t;i--)
    #define clr(x,c) memset(x,c,sizeof(x))
    int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){
    if(c=='-') f=-1;c=getchar();
    }
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*f;
    }
    const int nmax=25;
    const int inf=0x7f7f7f7f;
    int a[nmax],ans,cnt=0;
    void mins(int &a,int b){
    if(a>b) a=b;
    }
    void dfs(int tmp){
    if(tmp>=ans) return ;
    int cnt=0;
    rep(i,2,14) if(a[i]) cnt++;
    mins(ans,tmp+cnt);
    if(!cnt) return ;
    int ta[nmax]={0},tb[nmax]={0};
    rep(i,3,10){
    int cur=0;
    rep(j,i,14) if(!a[j]) {
    cur=j;break;
    }
    if(!cur) cur=15;--cur;
    if(cur-i+1>=5) {
    rep(j,i,i+3) a[j]--;
    rep(j,i+4,cur) a[j]--,dfs(tmp+1);
    rep(j,i,cur) a[j]++;
    }
    }
    rep(i,3,12){
    int cur=0;
    rep(j,i,14) if(a[j]<2){
    cur=j;break;
    }
    if(!cur) cur=15;--cur;
    if(cur-i+1>=3){
    rep(j,i,i+1) a[j]-=2;
    rep(j,i+2,cur) a[j]-=2,dfs(tmp+1);
    rep(j,i,cur) a[j]+=2;
    }
    }
    rep(i,3,13){
    int cur=0;
    rep(j,i,14) if(a[j]<3){
    cur=j;break;
    }
    if(!cur) cur=15;--cur;
    if(cur-i+1>=2){
    a[i]-=3;
    rep(j,i+1,cur) a[j]-=3,dfs(tmp+1);
    rep(j,i,cur) a[j]+=3;
    }
    }
    rep(i,2,14){
    if(a[i]>=3){
    int ca=0,cb=0;
    rep(j,2,14) if(j!=i&&a[j]>=2) ta[++ca]=j;
    rep(j,2,14) if(j!=i&&a[j]>=1) tb[++cb]=j;
    a[i]-=3;
    rep(j,1,ca){
    a[ta[j]]-=2;dfs(tmp+1);a[ta[j]]+=2;
    }
    rep(j,1,cb) {
    a[tb[j]]--;dfs(tmp+1);a[tb[j]]++;
    }
    a[i]+=3;
    if(a[i]==4){
    a[i]-=4;
    rep(j,1,ca-1) rep(k,j+1,ca) {
    a[ta[j]]-=2;a[ta[k]]-=2;
    dfs(tmp+1);a[ta[j]]+=2;a[ta[k]]+=2;
    }
    rep(j,1,cb-1) rep(k,j+1,cb) {
    a[tb[j]]--;a[tb[k]]--;
    dfs(tmp+1);a[tb[j]]++;a[tb[k]]++;
    }
    rep(j,1,ca){
    a[ta[j]]-=2;dfs(tmp+1);a[ta[j]]+=2;
    }
    a[i]+=4;
    }
    }
    }
    return ;
    }
    int main(){
    freopen("landlords.in","r",stdin);
    freopen("landlords.ans","w",stdout);
    int T=read(),n=read();
    while(T--){
    int u,v,d;ans=inf;clr(a,0);
    rep(i,1,n) {
    u=read(),v=read();
    if(u==0&&v==1) u=16;
    else if(u==0&&v==2) u=15;
    else if(u==1) u=14;
    a[u]++;
    }
    dfs(0);
    if(a[16]||a[15]) ans++;
    printf("%d\n",ans);
    }
    return 0;
    }

  • 0
    @ 2016-09-10 11:02:39

    提一点,顺子会影响出牌次数,如果忽略顺子不打,那么最少出牌次数是一定的。
    这样DFS都可以过了,用不上DP

  • 0
    @ 2016-04-02 21:50:26

    贴一段pascal的代码,基本思想是dfs+一点贪心思想(数据处理上有点复杂)
    var
    n,t,x,y,i,ans:longint;
    a:array[0..15] of longint;
    p:array[0..4] of longint;
    toe:array[1..3] of longint=(5,3,2);
    procedure dfs(an:longint);
    var i,j:longint;
    begin
    if an>=ans then exit;j:=0;
    for i:=1 to 4 do j:=j+p[i];
    if j+an<ans then ans:=j+an;
    if p[4]>0 then begin
    dec(p[4]);
    for i:=4 downto 2 do if p[i]>0 then begin
    dec(p[i]);inc(p[i-2]);
    for j:=2 to 4 do
    if p[j]>0 then begin
    dec(p[j]);inc(p[j-2]);
    dfs(an+1);
    inc(p[j]);dec(p[j-2]);
    end;
    inc(p[i]);dec(p[i-2]);
    end;
    for i:=1 to 4 do if p[i]>0 then begin
    dec(p[i]);inc(p[i-1]);
    for j:=1 to 4 do
    if p[j]>0 then begin
    dec(p[j]);inc(p[j-1]);
    dfs(an+1);
    inc(p[j]);dec(p[j-1]);
    end;
    inc(p[i]);dec(p[i-1]);
    end;
    i:=i;
    inc(p[4]);
    end;
    if p[3]>0 then begin
    dec(p[3]);
    for i:=2 to 4 do if p[i]>0 then begin
    dec(p[i]);inc(p[i-2]);dfs(an+1);inc(p[i]);dec(p[i-2]);
    end;
    for i:=1 to 4 do if p[i]>0 then begin
    dec(p[i]);inc(p[i-1]);dfs(an+1);inc(p[i]);dec(p[i-1]);
    end;
    inc(p[3]);
    end;
    end;
    procedure solve(an:longint);
    var i,j,k,jj:longint;
    begin
    if an>=ans then exit;
    fillchar(p,sizeof(p),0);
    for i:=1 to 15 do inc(p[a[i]]);
    if p[0]=15 then begin
    ans:=an;exit;
    end;
    dfs(an);
    for k:=1 to 3 do begin
    for i:=1 to 14-toe[k]-1 do
    if a[i]>=k then begin
    for j:=i+1 to 12 do
    if a[j]<k then break;
    if a[j]<k then dec(j);
    if j-i+1<toe[k] then continue;jj:=j;
    for j:=i to i+toe[k]-1 do dec(a[j],k);
    solve(an+1);
    for j:=i+toe[k] to jj do begin
    dec(a[j],k);
    solve(an+1);
    end;
    for j:=i to jj do inc(a[j],k);
    end;
    i:=i;
    end;
    end;
    begin
    readln(t,n);
    for t:=1 to t do begin
    ans:=13;
    fillchar(a,sizeof(a),0);
    for i:=1 to n do begin
    readln(x,y);
    if (x>=3)and(x<=13) then inc(a[x-2])
    else if x=1 then inc(a[12])
    else if x=2 then inc(a[13])
    else if y=1 then inc(a[14]) else inc(a[15]);
    end;
    if (a[14]>0)and(a[15]>0) then begin
    a[14]:=0;a[15]:=0;
    solve(1);
    a[14]:=1;a[15]:=1;
    end;
    solve(0);
    writeln(ans);
    end;
    end.

  • 0
    @ 2016-03-09 18:09:57

    测试数据 #0: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #1: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #2: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #3: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #4: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #5: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #6: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #7: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #8: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #9: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #10: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #11: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #12: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #13: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #14: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #15: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #16: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #17: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #18: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #19: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #20: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #21: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #22: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #23: Accepted, time = 0 ms, mem = 2516 KiB, score = 1

    测试数据 #24: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #25: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #26: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #27: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #28: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #29: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #30: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #31: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #32: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #33: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #34: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #35: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #36: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #37: Accepted, time = 15 ms, mem = 2516 KiB, score = 1

    测试数据 #38: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #39: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #40: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #41: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #42: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #43: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #44: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #45: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #46: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #47: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #48: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #49: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #50: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #51: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #52: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #53: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #54: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #55: Accepted, time = 31 ms, mem = 2512 KiB, score = 1

    测试数据 #56: Accepted, time = 31 ms, mem = 2508 KiB, score = 1

    测试数据 #57: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #58: Accepted, time = 15 ms, mem = 2516 KiB, score = 1

    测试数据 #59: Accepted, time = 31 ms, mem = 2512 KiB, score = 1

    测试数据 #60: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #61: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #62: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #63: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #64: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #65: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

    测试数据 #66: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #67: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #68: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

    测试数据 #69: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #70: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #71: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #72: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #73: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #74: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

    测试数据 #75: Accepted, time = 234 ms, mem = 2508 KiB, score = 1

    测试数据 #76: Accepted, time = 46 ms, mem = 2508 KiB, score = 1

    测试数据 #77: Accepted, time = 109 ms, mem = 2508 KiB, score = 1

    测试数据 #78: Accepted, time = 31 ms, mem = 2508 KiB, score = 1

    测试数据 #79: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

    测试数据 #80: Accepted, time = 93 ms, mem = 2512 KiB, score = 1

    测试数据 #81: Accepted, time = 62 ms, mem = 2512 KiB, score = 1

    测试数据 #82: Accepted, time = 125 ms, mem = 2512 KiB, score = 1

    测试数据 #83: Accepted, time = 46 ms, mem = 2508 KiB, score = 1

    测试数据 #84: Accepted, time = 46 ms, mem = 2508 KiB, score = 1

    测试数据 #85: Accepted, time = 218 ms, mem = 2508 KiB, score = 1

    测试数据 #86: Accepted, time = 187 ms, mem = 2508 KiB, score = 1

    测试数据 #87: Accepted, time = 156 ms, mem = 2512 KiB, score = 1

    测试数据 #88: Accepted, time = 453 ms, mem = 2512 KiB, score = 1

    测试数据 #89: Accepted, time = 187 ms, mem = 2512 KiB, score = 1

    测试数据 #90: Accepted, time = 578 ms, mem = 2508 KiB, score = 1

    测试数据 #91: Accepted, time = 703 ms, mem = 2512 KiB, score = 1

    测试数据 #92: Accepted, time = 765 ms, mem = 2512 KiB, score = 1

    测试数据 #93: Accepted, time = 109 ms, mem = 2508 KiB, score = 1

    测试数据 #94: Accepted, time = 328 ms, mem = 2508 KiB, score = 1

    测试数据 #95: Accepted, time = 265 ms, mem = 2508 KiB, score = 1

    测试数据 #96: Accepted, time = 359 ms, mem = 2508 KiB, score = 1

    测试数据 #97: Accepted, time = 421 ms, mem = 2512 KiB, score = 1

    测试数据 #98: WrongAnswer, time = 359 ms, mem = 2508 KiB, score = 0

    测试数据 #99: WrongAnswer, time = 546 ms, mem = 2512 KiB, score = 0

  • 0
    @ 2016-02-27 15:09:35

    dancing link 可做吗

  • 0
    @ 2016-01-09 04:25:44

    注意:题意的重点.
    2个王一般情况是不视作1对的.火箭不是对.
    4带2,可以带2个王.
    3带2,不可以带2个王.
    但是3带1,可以带1个王.

  • 0
    @ 2015-12-20 14:39:17

    memset有毒!!写了两个个多余的memset并且数组开大了8倍才40分,去掉了之后并且数组开小了一点就AC了......
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #define rep(i, x, y) for (int i = x; i <= y; ++i)
    #define dwn(i, x, y) for (int i = x; i >= y; --i)
    #define pu {temp = encode(tot); if (!vis[temp]) {vis[temp] = true; q[++tl] = temp; dist[tl] = dist[hd] + 1;}}
    #define INF 1 << 30

    using namespace std;

    const int maxs = 1 << 20;
    int T, n;
    int vis[maxs], dist[maxs];
    int inp[32];
    int dd[15], cnt[15];

    inline int encode(int *p) {
    int r = 0;
    rep(i, 0, 14) r += p[i] * dd[i];
    return r;
    }
    inline void decode(int x, int *p) {
    dwn(i, 14, 0) {p[i] = x / dd[i]; x %= dd[i];}
    }
    inline void calcu() {
    dd[0] = 1;
    rep(i, 1, 14) dd[i] = cnt[i - 1] * dd[i - 1];
    }
    int q[maxs << 1];
    int temp;
    inline int bfs(int x) {
    memset(vis, 0, sizeof (vis));
    int tot[15];
    int hd, tl;
    q[hd = tl = 0] = x;
    int s;
    int ans = INF;
    dist[0] = 0;
    while (hd <= tl) {
    s = q[hd];
    if (s == 0) {ans = min(ans, dist[hd]); ++hd; continue;}
    // vis[s] = true;
    decode(s, tot);
    bool f = false;
    int ccnt = 0;
    if (tot[13] && tot[14]) {
    tot[13] = tot[14] = 0;
    f = true;
    pu
    tot[13] = tot[14] = 1;
    }
    rep(i, 0, 14) {
    if (tot[i]) ++ccnt;
    if (tot[i] >= 4) {
    tot[i] -= 4;
    f = true;
    pu
    rep(j, 0, 14) if (tot[j]) {
    --tot[j];
    rep(k, 0, 14) if (tot[k]) {
    --tot[k];
    f = true;
    pu
    ++tot[k];
    }
    ++tot[j];
    }
    rep(j, 0, 14) if (tot[j] >= 2) {
    tot[j] -= 2;
    rep(k, 0, 14) if (tot[k] >= 2) {
    tot[k] -= 2;
    f = true;
    pu
    tot[k] += 2;
    }
    tot[j] += 2;
    }
    tot[i] += 4;
    }//zhadan and sidaier
    if (tot[i] >= 2) {
    tot[i] -= 2;
    f = true;
    pu
    tot[i] += 2;
    }//duizi

    if (tot[i] >= 3) {
    tot[i] -= 3;
    f = true;
    pu
    rep(j, 0, 14) {
    if (i == j) continue;
    if (tot[j] >= 1) {
    --tot[j];
    f = true;
    pu
    ++tot[j];
    }//sandaiyi
    if (tot[j] >= 2) {
    tot[j] -= 2;
    f = true;
    pu
    tot[j] += 2;
    }//sandaier
    }
    tot[i] += 3;
    }//sanzhang and sandaiyi, sandaier
    }
    int lianxu;
    rep(i, 0, 7) {
    lianxu = 0;
    rep(j, i, 11) if (tot[j] >= 1) ++lianxu; else break;
    if (lianxu >= 5) {
    rep(j, i, i + 3) --tot[j];
    rep(j, i + 4, i + lianxu - 1) {
    --tot[j];
    f = true;
    pu
    }
    rep(j, i, i + lianxu - 1) ++tot[j];
    }
    }//danshunzi
    rep(i, 0, 9) {
    lianxu = 0;
    rep(j, i, 11) if (tot[j] >= 2) ++lianxu; else break;
    if (lianxu >= 3) {
    rep(j, i, i + 1) tot[j] -= 2;
    rep(j, i + 2, i + lianxu - 1) {
    tot[j] -= 2;
    f = true;
    pu
    }
    rep(j, i, i + lianxu - 1) tot[j] += 2;
    }
    }//shuangshunzi
    rep(i, 0, 10) {
    lianxu = 0;
    rep(j, i, 11) if (tot[j] >= 3) ++lianxu; else break;
    if (lianxu >= 2) {
    tot[i] -= 3;
    rep(j, i + 1, i + lianxu - 1) {
    tot[j] -= 3;
    f = true;
    pu
    }
    rep(j, i, i + lianxu - 1) tot[j] += 3;
    }
    }//sanshunzi
    if (!f) ans = min(ans, dist[hd] + ccnt);
    ++hd;
    }
    return ans;
    }
    int xx, yy;
    inline void work() {
    memset(cnt, 0, sizeof (cnt));
    rep(i, 1, n) {
    scanf("%d %d", &xx, &yy);
    if (3 <= xx && xx <= 13) inp[i] = xx - 3;
    if (xx == 1) inp[i] = 11;
    if (xx == 2) inp[i] = 12;
    if (xx == 0 && yy == 1) inp[i] = 13;
    if (xx == 0 && yy == 2) inp[i] = 14;
    ++cnt[inp[i]];
    }
    rep(i, 0, 14) ++cnt[i];
    calcu();
    rep(i, 0, 14) --cnt[i];
    printf("%d\n", bfs(encode(cnt)));
    }
    int main(int argc, const char *argv[]) {
    scanf("%d %d", &T, &n);
    while (T--) work();
    return 0;
    }

  • 0
    @ 2015-11-25 17:23:42

    #include<cstdio>
    #include<algorithm>
    #define SC scanf
    #define U_(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    int s[14],ans;
    int t,n;
    void dfs(int now){
    if(now>=ans)return;
    int r=0,a=0,b=0;
    U_(i,0,13)if(s[i]==1)a++;
    U_(i,0,13)if(s[i]==2)b++;
    U_(i,0,13)if(s[i]==4){
    r++;
    if(a>=2)a-=2;else
    if(b>=2)b-=2;else
    if(b>=1)b--;
    }
    U_(i,0,13)if(s[i]==3){
    r++;
    if(a>=1)a--;else
    if(b>=1)b--;
    }
    ans=min(ans,now+r+a+b);
    int j;
    U_(i,0,7){
    for(j=i;j<12;j++){
    s[j]--;
    if(s[j]<0)break;
    if(j-i>=4)dfs(now+1);
    }
    if(j==12)j--;
    while(j>=i)s[j--]++;
    }
    U_(i,0,9){
    for(j=i;j<12;j++){
    s[j]-=2;
    if(s[j]<0)break;
    if(j-i>=2)dfs(now+1);
    }
    if(j==12)j--;
    while(j>=i)s[j--]+=2;
    }
    U_(i,0,10){
    for(j=i;j<12;j++){
    s[j]-=3;
    if(s[j]<0)break;
    if(j-i>=1)dfs(now+1);
    }
    if(j==12)j--;
    while(j>=i)s[j--]+=3;
    }
    }
    int main()
    {
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);

    SC("%d%d",&t,&n);
    while(t--){
    ans=100000;
    int a,b;
    U_(i,0,13)s[i]=0;
    U_(i,1,n){
    SC("%d%d",&a,&b);
    if(a==1)s[11]++;else
    if(a==2)s[12]++;else
    if(a==0)s[13]++;else
    s[a-3]++;
    }
    dfs(0);
    printf("%d\n",ans);
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
    }

  • 0
    @ 2015-11-25 17:23:16

    此程序在UOj和洛谷都过了;
    在这卡了一个点
    不要问我怎么做
    我只提供程序(不是我写的)
    搞不懂为什么

    • @ 2015-11-26 13:32:34

      实测发现,在那个点,双王被当成对子,被三带二或四带对搞掉了;强制双王单独出后可AC

信息

ID
1980
难度
8
分类
(无)
标签
递交数
2492
已通过
332
通过率
13%
上传者