2473: 【例】【普及-】【P1464】Function

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：24 解决：11

题目描述

对于一个递归函数 lns="http://www.w3.org/1998/Math/MathML">�(�,�,�)

  • 如果 lns="http://www.w3.org/1998/Math/MathML">�≤0 或 lns="http://www.w3.org/1998/Math/MathML">�≤0 或 lns="http://www.w3.org/1998/Math/MathML">�≤0 就返回值lns="http://www.w3.org/1998/Math/MathML">1。
  • 如果 lns="http://www.w3.org/1998/Math/MathML">�>20 或 lns="http://www.w3.org/1998/Math/MathML">�>20 或 lns="http://www.w3.org/1998/Math/MathML">�>20 就返回 lns="http://www.w3.org/1998/Math/MathML">�(20,20,20)
  • 如果 lns="http://www.w3.org/1998/Math/MathML">�<� 并且 lns="http://www.w3.org/1998/Math/MathML">�<� 就返回lns="http://www.w3.org/1998/Math/MathML">�(�,�,�−1)+�(�,�−1,�−1)−�(�,�−1,�)。
  • 其它的情况就返回 lns="http://www.w3.org/1998/Math/MathML">�(�−1,�,�)+�(�−1,�−1,�)+�(�−1,�,�−1)−�(�−1,�−1,�−1)

这是个简单的递归函数，但实现起来可能会有些问题。当 lns="http://www.w3.org/1998/Math/MathML">�,�,� 均为 lns="http://www.w3.org/1998/Math/MathML">15 时，调用的次数将非常的多。你要想个办法才行。

注意：例如 lns="http://www.w3.org/1998/Math/MathML">�(30,−1,0) 又满足条件 lns="http://www.w3.org/1998/Math/MathML">1 又满足条件 lns="http://www.w3.org/1998/Math/MathML">2，请按照最上面的条件来算，答案为 lns="http://www.w3.org/1998/Math/MathML">1。

输入

会有若干行。

并以 lns="http://www.w3.org/1998/Math/MathML">−1,−1,−1 结束。

输出

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

w(a, b, c) = ans

注意空格。

样例输入 复制 

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

样例输出 复制 

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

提示

数据规模与约定

保证输入的数在 lns="http://www.w3.org/1998/Math/MathML">[−9223372036854775808,9223372036854775807] 之间，并且是整数。

保证不包括 lns="http://www.w3.org/1998/Math/MathML">−1,−1,−1 的输入行数 lns="http://www.w3.org/1998/Math/MathML">� 满足 lns="http://www.w3.org/1998/Math/MathML">1≤�≤105。 

#include <bits/stdc++.h>

using namespace std;
long long x, y, z;
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(20, 20, 20);
    }
    if (a < b && b < c) {
        return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    }
    return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
    while (cin >> x >> y >> z) {
        if (x == -1 && y == -1 && x == -1) {
            break;
        }
        printf("w(%lld, %lld, %lld) = %lld\n", x, y, z, w(x, y, z));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long f[25][25][25];
long long w(long long a,long long b,long long c){
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return w(20,20,20);
    else if(f[a][ b ][c]!=0) return f[a][ b ][c];
    else if(a<b&&b<c)
        f[a][ b ][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else
	    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];
}


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

来源/分类

提交提交记录统计露一手!