louisfghbvc的部落格

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

題目大意:  問你k個骰字組出n的點數，幾種組合(不重複)，比如 3, 5 =>(1, 2, 2), (1, 1, 3) 2種。

思路:  枚舉，記憶化搜索，那可以發現說一定是一個絕對遞增或絕對遞減的數列。枚舉這個數列，要加快的話可以使用3維陣列

代碼1:  

#include <bits/stdc++.h>  
using namespace std;  
int dfs(int k, int x, int pre){  
    if(k > x) return 0;  
    if(k == 0){  
        if(x != 0) return 0;  
        return 1;  
    }  
    int res = 0;  
    for(int j = min(pre, 6); j >= 1; --j){  
        res += dfs(k-1, x-j, j);  
    }  
    return res;  
}  
int main()  
{  
    int k, n;  
  
    while(cin >> k >> n){  
        cout << dfs(k, n, n) << endl;  
    }  
    return 0;  
} 

代碼2: 加快

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

int dp[36][125][8];
int dfs(int k, int x, int pre){
    if(k > x) return 0;
    if(k == 0){
        if(x != 0) return 0;
        return 1;
    }
    if(dp[k][x][pre] != -1) return dp[k][x][pre];
    int res = 0;
    for(int j = pre; j >= 1; --j){
        res += dfs(k-1, x-j, j);
    }
    return dp[k][x][pre] = res;
}

int main()
{
    int k, n;
    memset(dp, -1, sizeof dp);
    while(cin >> k >> n){
        cout << dfs(k, n, min(n, 6)) << endl;
    }
    return 0;
}