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;
}