题解

题面描述

手上有一副扑克牌，每张牌按牌面数字记分（$J=11, Q=12, K=13$，没有大小王）。出牌时按照以下规则记分：

1. 出单张：记牌面分数，例如出一张 $2$，得分为 $2$。
2. 出对子或三张：记牌面分数总和再乘以 $2$，例如出 $3$ 张 $3$，得分为 $(3 + 3 + 3) \times 2 = 18$。
3. 出顺子（5 张连续的牌）：记牌面分数总和再乘以 $2$，例如出 $34567$ 顺，得分为 $(3 + 4 + 5 + 6 + 7) \times 2 = 50$。
4. 出炸弹（4 张相同的牌）：记牌面分数总和再乘以 $3$，例如出 $4$ 张 $4$，得分为 $4 \times 4 \times 3 = 48$。

求出一副牌的最高得分数。

思路

本题的核心是通过动态规划（DP）或记忆化搜索（DFS + Memoization）的方法，枚举所有可能的出牌组合，并选择得分最高的组合。具体步骤如下：

1. 牌面转换：将输入的牌面字符转换为对应的数值，便于后续处理。例如，J 转换为 $11$，Q 转换为 $12$，K 转换为 $13$，0 转换为 $10$。

2. 统计牌面数量：统计每种牌面出现的次数，存储在一个数组中。例如，counts[1] 表示牌面为 $1$ 的牌有几张，依此类推。

3. 动态规划：

   • 定义一个状态表示为当前各牌面剩余的数量。
   • 对于每种状态，尝试所有可能的出牌方式（单张、对子、三张、炸弹、顺子）。
   • 对于每种出牌方式，递归计算剩余牌组的最大得分，并更新当前状态的最大得分。
   • 使用记忆化缓存（如哈希表）来存储已经计算过的状态，避免重复计算。

4. 处理顺子：

   • 顺子需要 $5$ 张连续的牌，且不包含 10JQKA（即 0JQK1 不算顺）。
   • 枚举所有可能的起始牌面，检查是否满足顺子的条件。

cpp

#include <bits/stdc++.h>
using namespace std;

// 将牌面字符转换为对应的数值
int cardValue(char c){
    if(c >= '1' && c <= '9') return c - '0';
    if(c == '0') return 10;
    if(c == 'J') return 11;
    if(c == 'Q') return 12;
    if(c == 'K') return 13;
    return -1; // 不可能的情况
}

// 使用记忆化搜索的方式计算最大得分
unordered_map<string, long long> dp_cache;

// 计算最大得分的函数
long long dfs(vector<int> &counts){
    // 将当前状态转换为字符串作为缓存的键
    string key = "";
    for(auto cnt : counts) key += to_string(cnt) + ",";
    if(dp_cache.find(key) != dp_cache.end()) return dp_cache[key];
    
    long long res = 0;
    // 尝试所有可能的出牌方式

    // 1. 出单张
    for(int i=1;i<=13;i++) {
        if(counts[i] >=1){
            counts[i]--;
            res = max(res, (long long)i + dfs(counts));
            counts[i]++;
        }
    }

    // 2. 出对子
    for(int i=1;i<=13;i++) {
        if(counts[i] >=2){
            counts[i] -=2;
            res = max(res, (long long)(i*2)*2 + dfs(counts));
            counts[i] +=2;
        }
    }

    // 3. 出三张
    for(int i=1;i<=13;i++) {
        if(counts[i] >=3){
            counts[i] -=3;
            res = max(res, (long long)(i*3)*2 + dfs(counts));
            counts[i] +=3;
        }
    }

    // 4. 出炸弹
    for(int i=1;i<=13;i++) {
        if(counts[i] >=4){
            counts[i] -=4;
            res = max(res, (long long)(i*4)*3 + dfs(counts));
            counts[i] +=4;
        }
    }

    // 5. 出顺子
    // 顺子需要5张连续的牌，且不包含10JQKA（即0JQK1）
    for(int start=1; start<=9; start++){ // 13-5+1=9
        bool valid=true;
        for(int j=0; j<5; j++) {
            if(counts[start+j] <1){
                valid=false;
                break;
            }
        }
        // 检查是否包含1和13的情况（0JQK1不算顺）
        if(valid){
            // 如果包含1和13，则不算
            bool invalid = false;
            for(int j=0; j<5; j++){
                if((start + j) ==1 || (start + j) ==13){
                    invalid=true;
                    break;
                }
            }
            if(!invalid){
                // 计算顺子的总分
                int sum =0;
                for(int j=0; j<5; j++) sum += (start + j);
                // 出顺子
                for(int j=0; j<5; j++) counts[start + j]--;
                res = max(res, (long long)(sum)*2 + dfs(counts));
                for(int j=0; j<5; j++) counts[start + j]++;
            }
        }
    }

    dp_cache[key] = res;
    return res;
}

int main(){
    string s;
    cin >> s;
    // 初始化牌面计数
    vector<int> counts(14,0); // counts[1..13]
    for(char c: s){
        int val = cardValue(c);
        counts[val]++;
    }
    cout << dfs(counts) << endl;
}

python

from functools import lru_cache

# 将牌面字符转换为对应的数值
def card_value(c):
    if c.isdigit() and c != '0':
        return int(c)
    if c == '0':
        return 10
    if c == 'J':
        return 11
    if c == 'Q':
        return 12
    if c == 'K':
        return 13
    return -1  # 不可能的情况

def main():
    s = input().strip()
    counts = [0]*14  # counts[1..13]
    for c in s:
        val = card_value(c)
        counts[val] +=1

    @lru_cache(None)
    def dfs(state):
        counts = list(state)
        res = 0
        # 1. 出单张
        for i in range(1,14):
            if counts[i] >=1:
                counts[i] -=1
                res = max(res, i + dfs(tuple(counts)))
                counts[i] +=1
        # 2. 出对子
        for i in range(1,14):
            if counts[i] >=2:
                counts[i] -=2
                res = max(res, (i*2)*2 + dfs(tuple(counts)))
                counts[i] +=2
        # 3. 出三张
        for i in range(1,14):
            if counts[i] >=3:
                counts[i] -=3
                res = max(res, (i*3)*2 + dfs(tuple(counts)))
                counts[i] +=3
        # 4. 出炸弹
        for i in range(1,14):
            if counts[i] >=4:
                counts[i] -=4
                res = max(res, (i*4)*3 + dfs(tuple(counts)))
                counts[i] +=4
        # 5. 出顺子
        for start in range(1,10):
            valid = True
            for j in range(5):
                if counts[start+j] <1:
                    valid = False
                    break
            if valid:
                # 检查是否包含1和13
                invalid = False
                for j in range(5):
                    if (start+j)==1 or (start+j)==13:
                        invalid = True
                        break
                if not invalid:
                    sum_seq = sum(start + j for j in range(5))
                    for j in range(5):
                        counts[start+j] -=1
                    res = max(res, sum_seq*2 + dfs(tuple(counts)))
                    for j in range(5):
                        counts[start+j] +=1
        return res

    print(dfs(tuple(counts)))

if __name__ == "__main__":
    main()

java

import java.util.*;
public class Main {
    // 将牌面字符转换为对应的数值
    public static int cardValue(char c){
        if(c >= '1' && c <= '9') return c - '0';
        if(c == '0') return 10;
        if(c == 'J') return 11;
        if(c == 'Q') return 12;
        if(c == 'K') return 13;
        return -1; // 不可能的情况
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] counts = new int[14]; // counts[1..13]
        for(char c: s.toCharArray()){
            int val = cardValue(c);
            counts[val]++;
        }
        Map<String, Long> memo = new HashMap<>();
        System.out.println(dfs(counts, memo));
    }

    // 递归计算最大得分
    public static long dfs(int[] counts, Map<String, Long> memo){
        StringBuilder keyBuilder = new StringBuilder();
        for(int i=1;i<=13;i++) keyBuilder.append(counts[i]).append(",");
        String key = keyBuilder.toString();
        if(memo.containsKey(key)) return memo.get(key);
        long res = 0;
        // 1. 出单张
        for(int i=1;i<=13;i++){
            if(counts[i] >=1){
                counts[i]--;
                res = Math.max(res, i + dfs(counts, memo));
                counts[i]++;
            }
        }
        // 2. 出对子
        for(int i=1;i<=13;i++){
            if(counts[i] >=2){
                counts[i] -=2;
                res = Math.max(res, (long)(i*2)*2 + dfs(counts, memo));
                counts[i] +=2;
            }
        }
        // 3. 出三张
        for(int i=1;i<=13;i++){
            if(counts[i] >=3){
                counts[i] -=3;
                res = Math.max(res, (long)(i*3)*2 + dfs(counts, memo));
                counts[i] +=3;
            }
        }
        // 4. 出炸弹
        for(int i=1;i<=13;i++){
            if(counts[i] >=4){
                counts[i] -=4;
                res = Math.max(res, (long)(i*4)*3 + dfs(counts, memo));
                counts[i] +=4;
            }
        }
        // 5. 出顺子
        for(int start=1; start<=9; start++){
            boolean valid = true;
            for(int j=0; j<5; j++) {
                if(counts[start+j] <1){
                    valid = false;
                    break;
                }
            }
            if(valid){
                // 检查是否包含1和13
                boolean invalid = false;
                for(int j=0; j<5; j++){
                    if((start + j) ==1 || (start + j) ==13){
                        invalid = true;
                        break;
                    }
                }
                if(!invalid){
                    // 计算顺子的总分
                    int sum =0;
                    for(int j=0; j<5; j++) sum += (start + j);
                    // 出顺子
                    for(int j=0; j<5; j++) counts[start + j]--;
                    res = Math.max(res, (long)(sum)*2 + dfs(counts, memo));
                    for(int j=0; j<5; j++) counts[start + j]++;
                }
            }
        }
        memo.put(key, res);
        return res;
    }
}

题目内容

手上有一副扑克牌，每张牌按牌面数字记分（$J=11,Q=12,K=13，$没有大小王)，出牌时按照以下规则记分：

出单张，记牌面分数，例如出一张 $2$ ，得分为 $2$

出对或 $3$ 张，记牌面分数总和再 $×2$，例如出 $3$ 张 $3$ ，得分为 $(3+3+3)×2=18$

出 $5$ 张顺，记牌面分数总和再 $×2$ ，例如出 $34567$ 顺，得分为$(3+4+5+6+7)×2=50$

出 $4$ 张炸弹，记牌面分数总和再 $×3$ ，例如出 $4$ 张 $4$ ，得分为 $4×4×3=48$

求出一副牌最高的得分数

输入描述

按顺序排好的一副牌，最少 $1$ 张，最多 $15$ 张。

$1-9$ 输入为数字 $1-9$ ，$10$ 输入为数字 $0$ ，$JQK$ 输入为大写字母 $JQK$ .

无需考虑输入非法的情况，例如输入字符不在 $[0-9JQK]$ 范围或某一张牌超过 $4$ 张

输出描述

最高的得分数

备注

积分规则中没有的出牌方式不支持，例如不支持 $3$ 带 $1、4$ 带 $2$ ，不支持 $5$ 张以上的顺，且 $10JQKA$ $(0JQK1)$ 不算顺。

样例1

输入

33445677

输出

67

说明

出对 $3$、对 $4$、对 $7$，单张 $5、6$，得分为 $67$;

出 $34567$ 顺，再出单张 $3、4、7$，得分为 $64$

因此最高得分是按对出，可得到最高分 $67$ ，输出结果 $67$