洛谷P1464 Function

题目

输入格式

会有若干行。

并以-1,-1,-1结束。

保证输入的数在[-9223372036854775808,9223372036854775807]之间，并且是整数。

输出格式

输出若干行，每一行格式：

w(a, b, c) = ans

注意空格。

输入输出

输入

1 1 1
2 2 2
-1 -1 -1

输出

w(1, 1, 1) = 2
w(2, 2, 2) = 4

说明/提示

记忆化搜索

原题地址–>link

分析

刚开始以为要递归改为非递归，如果这样的话会很麻烦。最后题目提示，记忆化搜索。先说一下记忆化搜索。
百度百科解释：一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。
简单地说，就是将频率大的数据，放在数组中，再遇到就直接取，大大降低了时间复杂度！

Code

#include <iostream>
#define Is_w(a,b,c) (f[a][b][c]?f[a][b][c]:f[a][b][c]=w(a,b,c))
using namespace std;
long int f[21][21][21];//全局变量自动化初始为0
long int  w(long int a,long int b,long int c)
{
   
    if(a<=0||b<=0||c<=0) return 1;
    if(a>20||b>20||c>20) return Is_w(20,20,20);
    if(a<b&&b<c) return (Is_w(a,b,c-1)+Is_w(a,b-1,c-1)-Is_w(a,b-1,c));
    return Is_w(a-1,b,c)+Is_w(a-1,b-1,c)+Is_w(a-1,b,c-1)-Is_w(a-1,b-1,c-1);
}
int main()
{
   
    long int a,b,c;
    while (true)
    {
   
        cin>> a >> b >> c;
        if(a==-1&&b==-1&&c==-1) break;
        else
        {
   
            cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a,b,c) << endl;
        }
    }
    return 0;
}