louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=36186

題目大意:  問不重複出拳組合數，以及最大合群數(最多人出的拳種)。

思路:  枚舉，因為狀態皆為不重複情況，且沒有重複利用。所以沒有做記憶化搜索。

枚舉 5, 2, 0。保持著單調遞減關係，能讓狀態維持不重複組合。若是剩餘0，而且每個人都出拳了， 代表1種組合。

在出拳過程中，計算哪種拳出了幾次。最後紀錄組合時，就能知道最大合群數。並讓最大合群數>=2

代碼:  

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

int cc[3] = {5, 2, 0};
int cnt[3];
int n, x, y, mx;
int dfs(int id, int sum, int p){
    if(id > x || sum < 0) return 0;
    if(id == x && sum == 0){
        mx = max(mx, *max_element(cnt, cnt+3));
        if(mx < 2) mx = 0;
        return 1;
    }
    int res = 0;
    for(int i = p; i < 3; ++i){
        cnt[i]++;
        res += dfs(id+1, sum-cc[i], i);
        cnt[i]--;
    }
    return res;
}

int main()
{
    cin >> n;
    while(n--){
        memset(cnt, 0, sizeof cnt);
        mx = 0;
        cin >> x >> y;
        int v = dfs(0, y, 0);
        if(!v) puts("-1");
        else if(!mx) puts("0");
        else
            printf("%d %d\n", v, mx);
    }
    return 0;
}