为什么顺子一定要递归啊?在线等,急!
查看原帖
为什么顺子一定要递归啊?在线等,急!
675208
coder2009楼主2023/10/2 10:56

感觉我本人就是写了一个巨大的贪心,顺子走到不能走为止就去判断够不够条件,够就一口气打完,不够就后面当散牌出了,实在不明白题解里为什么全用了递归,蒟蒻真的不理解啊

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

int cnt[16], x = 0;

int dfs() {
    int k = 0;
    for (int i = 3; i <= 14; ++i) {
        if (cnt[i] >= 3) {
            ++k;
        } else {
            if (k >= 2) {
                for (int j = i; j >= i - k + 1; --j) {
                    cnt[j] -= 3;
                }
                ++x;
            }
            k = 0;
        }

    }
    k = 0;
    for (int i = 3; i <= 14; ++i) {
        if (cnt[i] >= 2) {
            ++k;
        }else {
            if (k >= 3) {
                for (int j = i; j >= i - k + 1; --j) {
                    cnt[j] -= 2;
                }
                ++x;
            }
            k = 0;
        }
    }
    k = 0;
    for (int i = 3; i <= 14; ++i) {
        if (cnt[i] >= 1) {
            ++k;
        } else {
            if (k >= 5) {
                for (int j = i; j >= i - k + 1; --j) {
                    cnt[j] -= 1;
                }
                ++x;
            }
            k = 0;
        }
    }
    int one = 0;
    int two = 0;
    if (cnt[0] == 1 && cnt[15] == 1) {
        ++two;
    } else if (cnt[0] == 1 || cnt[15] == 1) {
        ++one;
    }
    cnt[0] = 0;
    cnt[15] = 0;
    for (int i = 2; i <= 14; ++i) {
        if(cnt[i] == 4) {
            ++x;
            cnt[i] = 0;
            if (two >= 2) {
                two -= 2;
            } else if (one >= 2) {
                one -= 2;
            }
        }
        if (cnt[i] == 3) {
            ++x;
            cnt[i] = 0;
            if (two >= 1) {
                --two;
            } else if (one >= 1) {
                --one;
            }
        }
        if (cnt[i] == 1) {
            ++one;
            cnt[i] = 0;
        } else if (cnt[i] == 2){
            ++two;
            cnt[i] = 0;
        }
    }
    x += one;
    x += two;
    return x;
}

int main() {
    int t, n;
    cin >> t >> n;
    while(t--) {
        for (int i = 0; i < n; ++i) {
            int a, b;
            cin >> a >> b;
            if (a == 0 && b == 1) {
                ++cnt[0];
            } else if(a == 0 && b == 2) {
                ++cnt[15];
            } else if(a == 1) {
                ++cnt[14];
            } else {
                ++cnt[a];
            }
        }
        cout << dfs() << '\n';
        x = 0;
    }
    return 0;
}
2023/10/2 10:56
加载中...