前言：调了3h（洛谷）

传送门

思路

首先发现，只有打顺子时与大小有关，其他与牌的大小无关。

所以可以搜索如何打顺子，dp打其他牌。

搜索

搜索很简单，贴个代码：

void dfs(int x){
    if(x>=ans){//剪枝
        return;
    }
    memset(c,0,sizeof(c));
    for(int i=2;i<=14;i++){//统计每种牌的出现次数，c[1]表示单牌，c[2]表示对牌，c[3]表示三张牌，c[4]表示炸弹
        c[s[i]]++;
    }
    /*
    下面的dp一会讲
    */
    ans = min(ans,x+f[c[1]+s[0]][c[2]][c[3]][c[4]]);//顺便处理王牌：当做单牌出
    if(s[0]>=2){
        ans = min(ans,x+f[c[1]][c[2]][c[3]][c[4]]+1);//当做火箭（对牌）单出
    }
    for(int a=1;a<=3;a++){//枚举顺子：单顺，双顺，三顺
        for(int i=3;i<=14;i++){//枚举开头，特殊说明：14表示Ase，2不能在顺子里。
            int cnt = 0;//统计顺子里有多少牌
            for(int j=i;j<=14;j++){//枚举结尾
                if(s[j]>=a){//这种牌可以在顺子内
                    cnt+=a;//增加牌数
                }
                else{//否则就不连着了，直接break掉
                    break;
                }
                if(cnt>=5){//如果可以打顺子
                    for(int k=i;k<=j;k++){//打顺子
                        s[k]-=a;
                    }
                    dfs(x+1);//搜索
                    for(int k=i;k<=j;k++){//回溯
                        s[k]+=a;
                    }
                }
            }
        }
    }
}

dp

做一个 $4$ 维dp，$f_{a_{b_{c_d}}}$ 表示在还剩 $a$ 张单牌，$b$ 个对子，$c$ 个三张，$d$ 个炸弹时最少需要多少步才能打完。

给一个转移表格。

当然，这样是错的。

给个反例：$JJJ$ $QQQ$ $KKK$。

如果按刚才那样打的话，需要三步才能打完(打三次三张牌)，但实际上我们可以 拆牌（打一次三带一，打一次三带二）。

再给一个拆牌的转移表格。

其中将三张牌拆成三张单牌可以先将三张牌拆成一单一对，再将对牌拆成两张单牌，因此不用单独写一个转移。

把炸弹拆成四张单牌同理。

特别注意：拆牌不耗步数，小心数组越界

上代码！

    //初始化
    memset(f,0x3f,sizeof(f));
    f[0][0][0][0] = 0;
    //开始dp
    for(int d=0;d<=5;d++){//枚举炸弹个数
        for(int c=0;c<=7;c++){//枚举三张牌个数
            for(int b=0;b<=11;b++){//枚举对牌个数
                for(int a=0;a<=23;a++){//枚举单牌个数
                    //就是上面的循环边界浪费了我2h
                    if(a+b*2+c*3+d*4>n){//牌可以打出（减少），但不能凭空变出来（增多）
                        continue;
                    }
                    //打牌，注意不要越界
                    if(a>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a-1][b][c][d]+1);
                    }
                    if(b>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b-1][c][d]+1);
                    }
                    if(c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b][c-1][d]+1);
                    }
                    if(d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b][c][d-1]+1);
                    }
                    if(a>0 && c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a-1][b][c-1][d]+1);
                    }
                    if(b>0 && c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b-1][c-1][d]+1);
                    }
                    if(a>1 && d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a-2][b][c][d-1]+1);
                    }
                    if(b>1 && d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b-2][c][d-1]+1);
                    }
                    //拆牌，同样不能越界
                    if(b>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a+2][b-1][c][d]);
                    }
                    if(c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a+1][b+1][c-1][d]);
                    }
                    if(d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b+2][c][d-1]);
                    }
                    if(d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a+1][b][c+1][d-1]);
                    }
                }
            }
        }
    }

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,ans;
bool flag;
int s[25],c[25],f[30][30][30][30];
void dfs(int x){
    if(x>=ans){//剪枝
        return;
    }
    memset(c,0,sizeof(c));
    for(int i=2;i<=14;i++){//统计每种牌的出现次数，c[1]表示单牌，c[2]表示对牌，c[3]表示三张牌，c[4]表示炸弹
        c[s[i]]++;
    }
    /*
    下面的dp一会讲
    */
    ans = min(ans,x+f[c[1]+s[0]][c[2]][c[3]][c[4]]);//顺便处理王牌：当做单牌出
    if(s[0]>=2){
        ans = min(ans,x+f[c[1]][c[2]][c[3]][c[4]]+1);//当做火箭（对牌）单出
    }
    for(int a=1;a<=3;a++){//枚举顺子：单顺，双顺，三顺
        for(int i=3;i<=14;i++){//枚举开头，特殊说明：14表示Ase，2不能在顺子里。
            int cnt = 0;//统计顺子里有多少牌
            for(int j=i;j<=14;j++){//枚举结尾
                if(s[j]>=a){//这种牌可以在顺子内
                    cnt+=a;//增加牌数
                }
                else{//否则就不连着了，直接break掉
                    break;
                }
                if(cnt>=5){//如果可以打顺子
                    for(int k=i;k<=j;k++){//打顺子
                        s[k]-=a;
                    }
                    dfs(x+1);//搜索
                    for(int k=i;k<=j;k++){//回溯
                        s[k]+=a;
                    }
                }
            }
        }
    }
}
signed main(){
    cin >> t >> n;
    //初始化
    memset(f,0x3f,sizeof(f));
    f[0][0][0][0] = 0;
    //开始dp
    for(int d=0;d<=5;d++){//枚举炸弹个数
        for(int c=0;c<=7;c++){//枚举三张牌个数
            for(int b=0;b<=11;b++){//枚举对牌个数
                for(int a=0;a<=23;a++){//枚举单牌个数
                    //就是上面的循环边界浪费了我2h
                    if(a+b*2+c*3+d*4>n){//牌可以打出（减少），但不能凭空变出来（增多）
                        continue;
                    }
                    //打牌，注意不要越界
                    if(a>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a-1][b][c][d]+1);
                    }
                    if(b>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b-1][c][d]+1);
                    }
                    if(c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b][c-1][d]+1);
                    }
                    if(d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b][c][d-1]+1);
                    }
                    if(a>0 && c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a-1][b][c-1][d]+1);
                    }
                    if(b>0 && c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b-1][c-1][d]+1);
                    }
                    if(a>1 && d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a-2][b][c][d-1]+1);
                    }
                    if(b>1 && d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b-2][c][d-1]+1);
                    }
                    //拆牌，同样不能越界
                    if(b>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a+2][b-1][c][d]);
                    }
                    if(c>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a+1][b+1][c-1][d]);
                    }
                    if(d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a][b+2][c][d-1]);
                    }
                    if(d>0){
                        f[a][b][c][d] = min(f[a][b][c][d],f[a+1][b][c+1][d-1]);
                    }
                }
            }
        }
    }
    while(t--){
        memset(s,0,sizeof(s));
        ans = n;
        for(int i=1;i<=n;i++){
            int x,y;
            cin >> x >> y;
            if(x==1){//统计每种牌的数量，14号牌表示Ase
                s[14]++;
            }
            else{
                s[x]++;
            }
        }
        dfs(0);
        cout << ans << endl;
    }
    return 0;
}