洛谷 P1464 Function【动态规划(递推)/记忆化搜索(递归)】

时间:2024-09-14 11:05:38

题目描述

对于一个递归函数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)

这是个简单的递归函数,但实现起来可能会有些问题。当a,b,c均为15时,调用的次数将非常的多。你要想个办法才行.

/*

absi2011 : 比如 w(30,-1,0)既满足条件1又满足条件2

这种时候我们就按最上面的条件来算

所以答案为1

*/

输入输出格式

输入格式:

会有若干行.

并以-1,-1,-1结束.

保证输入的数在-9223372036854775808~9223372036854775807之间

并且是整数

输出格式:

输出若干行

格式:

[b]w(a,_b,_c)_=_你的输出(_代表空格)[/b]

输入输出样例

输入样例#1:
复制
1 1 1
2 2 2
-1 -1 -1
输出样例#1: 复制
w(1, 1, 1) = 2
w(2, 2, 2) = 4

【分析】:注释

【代码】:
#include<bits/stdc++.h>

using namespace std;
const int N = ;
int w[N][N][N];
int main()
{
int a,b,c; for(int a=;a<=;a++){
for(int b=;b<=;b++){
for(int c=;c<=;c++){
if(a<= || b<= || c<=) w[a][b][c]=;
else if(a> || b> || c>) w[a][b][c]=w[][][];
else if(a<b && b<c) w[a][b][c]=w[a][b][c-]+w[a][b-][c-]-w[a][b-][c];
else w[a][b][c]=w[a-][b][c]+w[a-][b-][c]+w[a-][b][c-]-w[a-][b-][c-];
}
}
} while(~scanf("%d%d%d",&a,&b,&c))
{
if(a==-&&b==-&&c==-) break;
//一定要分类特判输出
else if(a<= || b<= || c<=) printf("w(%d, %d, %d) = %d\n",a,b,c,);
else if(a>||b>||c>) printf("w(%d, %d, %d) = %d\n",a,b,c,w[][][]);
else printf("w(%d, %d, %d) = %d\n",a,b,c,w[a][b][c]);//不能直接只输出这一句
}
} /*
0 0 0
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
17 17 18
19 17 18
21 -21 20
-1 -1 -11
-1 -1 -1
*/ /*
w(0, 0, 0) = 1
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
w(17, 17, 18) = 131072
w(19, 17, 18) = 524271
w(21, -21, 20) = 1
w(-1, -1, -11) = 1
*/

DP递推