洛谷p1464-Function

题目链接

题解一：
思路：
题意是输入若干行，其结束标识是输入”-1 -1 -1”。
关键思想是使用：记忆化搜索，即开一个数组来存储一些数据。所谓记忆话搜索，就是对于你求的解，将他们的值都存在数组中，如果在搜索的过程中，这个解已经被计算过存储在了数组中，就不再需要计算了，直接返回f数组中对应的存储好的解。如果没有既定存储好的，就计算，存在f数组中。

由题意可以知道：
如果a,b,c有一个小于0，就返回1; (case 1)
如果a,b,c有一个大于20，就返回w(20，20，20); (case 2)
如果a<b且b<c就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c); (case 3)
如果其他的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c) (case 4)
可以发现，要开一个数组来存储这些返回值的话：这个数组的大小只要f[25][25][25]足够，就可以把所以的不同的情况都保存起来。

代码：

#include<bits/stdc++.h>
using namespace std;
long long f[25][25][25];
long long w(long a,long b,long c){
    if(a<=0||b<=0||c<=0)    return 1;//case 1
    if(a>20||b>20||c>20)    return w(20,20,20); //case 2
    else if(a<b&&b<c){  //case 3
        if(f[a][b][c]==-1)//判断这个记忆数组有没有已经存储，
            f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//就将结果存在对应的f数组中
    }
    else if(f[a][b][c]==-1){//case 4
        f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
    return f[a][b][c];//已经通过计算存在了f数组中，不需要计算，直接返回就行
}
int main(){
    memset(f,-1,sizeof(f));//先将f数组初始化全为-1
    long long a,b,c;
    do{
        cin>>a>>b>>c;//输入三个数字
        if(a!=-1||b!=-1||c!=-1)//这里检验一下是否为结素标志是因为，do-while循环会直接循环一次，
//这里写这句话是为了如果输入第一行时就输入：-1 -1 -1，就一次循环都不做。
            printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
    }while(a!=-1||b!=-1||c!=-1);//只要有一个不为-1，说明就不是结束标识，就可以继续输入
    return 0;
}