[TOC]

hankin练习3

我有太多事情需要去做，以后有时间再看问题所在。

#

#if 10
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;

LL C[105][105];
void combine()
{
    for (int i = 1; i < 105; i++) {
        C[i][0] = 1;
        C[i][1] = i;
        C[i][i] = 1;
        for (int j = 2; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return;
}

LL A(int n)
{
    LL ret = 1;
    for (int i = 2; i <= n; i++) {
        ret *= i;
    }
    return ret;
}

LL compute(LL i, LL j, LL k)
{
    LL x = max(max(i, j), k);
    LL y = min(min(i, j), k);
    LL z = i + j + k - x - y;
    LL ans1 = 0, ans2 = 0;
    for (int l = z; l > 0; l--) {
        ans1 += C[x + 1][l];
    }
    for (int l = y; l > 0; l--) {
        ans2 += C[x + z + 1][l];
    }
    //cout << ans1 << ' ' << ans2 << endl;
    if (ans1 == 0) ans1 = 1;
    if (ans2 == 0) ans2 = 1;
    return ans1 * ans2;
}

// 猜不透：只算组合数量--算上相同高度有区别--长宽高肯定不相等吧--居然忘记从0开始
int main()
{
    combine();
    LL N, x, y, z, ans = 0;
    cin >> N >> x >> y >> z;
    for (LL i = 0; i <= 100; i++) {
        if (i * x > N) break;
        for (LL j = 0; j <= 100; j++) {
            if (i * x + y * j > N) break;
            for (LL k = 0; k <= 100; k++) {
                LL cur = i * x + y * j + z * k;
                if (cur > N) break;
                if (cur == N) {
                    ans += compute(i, j, k);
                    //ans++;
                    break;
                }
            }
        }
    }
    cout << ans << endl;
    system("pause");
    return 0;
}
#endif

正确答案

#if 0
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;


int main()
{
    LL dp[105][105] = { 1 };
    LL N, x, y, z, ans = 0;
    cin >> N >> x >> y >> z;

    for (int i = 1; i < 105; i++) {
        for (int j = 0; j < 105; j++) {
            if (j - x >= 0) dp[i][j] += dp[i - 1][j - x];
            if (j - y >= 0) dp[i][j] += dp[i - 1][j - y];
            if (j - z >= 0) dp[i][j] += dp[i - 1][j - z];
        }
    }
    for (int i = 1; i < 105; i++) {
        ans += dp[i][N];
    }
    cout << ans << endl;
    system("pause");
    return 0;
}
#endif