題目描述

題目描述

解析：這題屬于遞歸問(wèn)題，如果直接遞歸求值會(huì)導(dǎo)致超時(shí)問(wèn)題，需要用記憶化搜索的方法，用空間換取時(shí)間。

記憶化搜索在求解的時(shí)候還是按著自頂向下的順序，但是每求解一個(gè)狀態(tài)，就將它的解保存下來(lái)，（用數(shù)組存儲(chǔ)）

以后再次遇到這個(gè)狀態(tài)的時(shí)候，就不必重新求解了。

這種方法綜合了搜索和動(dòng)態(tài)規(guī)劃兩方面的優(yōu)點(diǎn)，因而還是很有實(shí)用價(jià)值的。

本題通過(guò)數(shù)組long long w_mem[25][25][25];存儲(chǔ)解數(shù)據(jù)。

若遇到為求過(guò)的w則先賦值給w然后再返回，若求過(guò)則直接返回。

結(jié)合宏定義（記憶宏）的方法
我們加入這樣一個(gè)語(yǔ)句

#define W_MEM(x,y,z) (w_mem[x][y][z] ? w_mem[x][y][z] : w_mem[x][y][z] = w(x,y,z))

就可以簡(jiǎn)化代碼了。

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

#define W_MEM(x,y,z) (w_mem[x][y][z] ? w_mem[x][y][z] : w_mem[x][y][z] = w(x,y,z))

long long w_mem[25][25][25];

long long w(long long a,long long b,long long c)
{
    if(a <= 0 || b <= 0 || c <= 0)
    {
        return 1;
    }
    if(a > 20 || b > 20 || c > 20)
    {
        return W_MEM(20,20,20);
    }
    if(a < b && b < c)
    {
        return W_MEM(a,b,c-1) + W_MEM(a,b-1,c-1) - W_MEM(a,b-1,c);
    }
    return W_MEM(a-1,b,c) + W_MEM(a-1,b-1,c) + W_MEM(a-1,b,c-1) - W_MEM(a-1,b-1,c-1);
}

int main()
{
    string input;
    while(getline(cin,input))
    {
        stringstream ss(input);
        long long a,b,c;
        ss>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)
        {
            break;
        }
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<endl;
    }
    return 0;
}