题解 P2540 【斗地主增强版】

2017-10-28 11:40:57


这里提供一个双搜索的方法

第一个:搜索顺子(我的dfs函数)

第二个:记忆化搜索,没有顺子最多出几次(我的dfs2)(有人用贪心或dp做的)

代码ugly,dalao不要喷

#include<bits/stdc++.h>
using namespace std;
#define MAXN 31
#define INF 0x3f3f3f3f

int a[MAXN],b[MAXN],t[MAXN];
int n,m,ans = INF;
int c[MAXN];

int f[24][24][24][24];

int dfs2(int i,int j,int k,int l)//i个4,j个3,k个2,l个1 
{
    if(i<0||j<0||k<0||l<0) return INF;//出界无解,返回无穷 
    if(f[i][j][k][l] != 0) return f[i][j][k][l];
    int r = i+j+k+l;
    r = min(r,dfs2(i-1,j,k,l-2)+1);//4&2
    r = min(r,dfs2(i-1,j,k-1,l)+1);//4&2(1:2 2:2)
    r = min(r,dfs2(i-1,j-1,k,l+1)+1);//4&2(1:3 2:3)
    r = min(r,dfs2(i-1,j,k-2,l)+1);//4&2*2
    r = min(r,dfs2(i-1,j-1,k-1,l+1)+1);//4&2*2
    r = min(r,dfs2(i-2,j,k,l)+1);//4&2*2
      r = min(r,dfs2(i-1,j+1,k,l+1));//手动拆弹 
    r = min(r,dfs2(i,j-1,k-1,l)+1);//3&2
    r = min(r,dfs2(i,j-2,k,l+1)+1);//3&2
      r = min(r,dfs2(i,j-1,k,l-1)+1);//3&1
     r = min(r,dfs2(i,j-1,k-1,l+1)+1);//3&1
      r = min(r,dfs2(i,j-2,k+1,l)+1);//3&1
    f[i][j][k][l] = r;
    return r;
}

int tx() 
{
    memset(c,0,sizeof(c));
    int ans = 0;
    int k = 0;
    for(int i = 1;i <= 13;i ++) 
        c[t[i]] ++;
    k = t[14] + t[15];//王的数量 
    if(k == 0)
        return dfs2(c[4],c[3],c[2],c[1]);
    if(k == 1)
        return dfs2(c[4],c[3],c[2],c[1]+1);
    if(k == 2)
        return min(dfs2(c[4],c[3],c[2],c[1]+2),dfs2(c[4],c[3],c[2],c[1])+1);
}

const int fz[4] = {0,5,3,2}; 
int sd[105];

void dfs(int x)
{
    if(x > ans) return; 
    int o = tx();
    int p = 0;
    int l = 0,j;
    if(x + o < ans)
        ans = x + o;
    for(int ss = 1; ss <= 3; ss ++) 
    {
    for(int i = 3; i <= 15 - fz[ss]; i ++)
    {
        p = 1;
        j = i;   
        if(t[i] >= ss)
        {
            while(1)
            {
                j ++;
                 if(j > 13) l = 1;
                 else l = j;
                 if(j == 15)
                     break;
                 p ++;

                 if(t[l] < ss)
                 {
                     p --;
                    break;
                 }        
            }
        }

        if(p >= fz[ss])
        {
            for(int j = i; j <= i + fz[ss] - 1; j ++){
                if(j > 13) l = 1;
                else l = j;
                t[l] -= ss;
            }
            dfs(x+1);
            for(int j = i+fz[ss]; j <= i+p-1; j ++){
                if(j > 13) l = 1;
                else l = j;
                t[l] -= ss;
                dfs(x + 1);
            }

            for(int j = i; j <= i + p-1; j ++){
                if(j > 13) l = 1;
                    else l = j;
                t[l] += ss;
            }
        }
    }
    }

}

int main()
{

        scanf("%d%d",&m,&n);
        for(int tt = 1; tt <= m; tt ++)
        {
            ans = INF;
                memset(t,0,sizeof(t));
                for(int i = 1; i <= n; i ++)
                {
                        scanf("%d%d",&a[i],&b[i]);
                        if(a[i] != 0)
                        {
                            t[a[i]] ++;
                        }        
                        else
                            t[13+b[i]] ++;
                }
                dfs(0);
                printf("%d\n",ans);
        }
        return 0;
}