【題解】ZeroJudge b232: TOI2009 第四題:分房子

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b232

#include <iostream>
using namespace std;

long long m, n, dp[755][755];

long long f(int x, int lim){
    if (dp[x][lim]) return dp[x][lim];
    if (!x) return dp[x][lim] = 1;
    if (x && !lim) return dp[x][lim] = 0;
    if (lim % 2 == 0) return dp[x][lim] = f(x, lim-1);
    dp[x][lim] = f(x, lim-1);
    if (lim <= x) dp[x][lim] += f(x-lim, lim);
    return dp[x][lim];
}


int main() {
    cin >> m;
    for (int i = 0; i < m; i++){
        cin >> n;
        cout << f(n, n) << "\n";
    }
}
分享本文 Share with friends