codevs 1910 递归函数

2016-07-24  本文已影响237人  科学旅行者

题目:

题目描述 Description
对于一个递归函数w(a, b, c)。
如果a <= 0 or b <= 0 or c <= 0就返回值1。
如果a > 20 or b > 20 or c > 20就返回W(20,20,20)。
如果a < b并且b < c 就返回w(a, b, c − 1) + w(a, b − 1, c − 1) − w(a, b − 1, 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)
这是个简单的递归函数,但实现起来可能会有些问题。
输入描述 Input Description
会有若干行.每行三个数,表示a, b, c。并以−1, −1, −1结束
输出描述 Output Description
输出若干行,注意各种中的空格。
样例输入 Sample Input
1 1 1
2 2 2
-1 -1 -1
样例输出 Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
数据范围及提示 Data Size & Hint
a, b, c < 30, Task < 11

这道题给了递归函数,但是直接递归肯定超时(题目只给1s)。
此题可以在递归的过程中使用记忆化搜索,将已经求到的值存入一个数组,下一次到这里可以直接使用此数据而无需递归,减少递归次数。
注意:此题的a,b,c可能会小于0.

参考代码:

#include <iostream>
using namespace std;
int dp[35][35][35];
int w(int a,int b,int c) {
    if (a <= 0 || b <= 0 || c <= 0) {
        return 1;
    }
    else if (a > 20 || b > 20 || c > 20) {
        if (dp[a][b][c] == -100)
            dp[a][b][c] = w(20,20,20);
        return dp[a][b][c];
    }
    else if (a < b && b < c) {
        if (dp[a][b][c-1] == -100)
            dp[a][b][c-1] = w(a,b,c-1);
        if (dp[a][b-1][c-1] == -100)
            dp[a][b-1][c-1] = w(a,b-1,c-1);
        if (dp[a][b-1][c] == -100)
            dp[a][b-1][c] = w(a,b-1,c);
        return (dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c]);
    }
    else {
        if (dp[a-1][b][c] == -100)
            dp[a-1][b][c] = w(a-1,b,c);
        if (dp[a-1][b-1][c] == -100)
            dp[a-1][b-1][c] = w(a-1,b-1,c);
        if (dp[a-1][b][c-1] == -100)
        dp[a-1][b][c-1] = w(a-1,b,c-1);
        if (dp[a-1][b-1][c-1] == -100)
            dp[a-1][b-1][c-1] = w(a-1,b-1,c-1);
        return (dp[a-1][b][c]+dp[a-1][b-1][c]+dp[a-1][b][c-1]-
                dp[a-1][b-1][c-1]);
    }
}
int main() {
    int a,b,c;
    for (int i = 0;i < 35;++i) {
        for (int j = 0;j < 35;j++) {
            for (int k = 0;k < 35;k++) {
                dp[i][j][k] = -100;
            }
        }
    }
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
        int res = w(a,b,c);
        cout << "w" << "(" << a << ", " << b << ", " << c << ")" << " = " << res << endl;
    }
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读