记忆化搜索 dp学习~2
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1331
Function Run Fun
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3459 Accepted Submission(s): 1707
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ;
int dp[N][N][N]; void init()
{
memset(dp,-,sizeof(dp));
for(int i = ; i <= ; i++)
{
for(int j = ; j <=; j++)
{
dp[][i][j] = dp[i][j][] = dp[i][][j] = ;
}
}
}
int w(int a, int b, int c)
{
if(dp[a][b][c]!=-) return dp[a][b][c];
if(a<b&&b<c){
return dp[a][b][c] = w(a,b,c-)+w(a,b-,c-)-w(a,b-,c);
}
else return dp[a][b][c] = w(a-, b, c) + w(a-, b-, c) + w(a-, b, c-) - w(a-, b-, c-);
}
int main()
{
init();
int a, b, c;
while(~scanf("%d%d%d",&a,&b,&c))
{
//printf("w = %d\n",w(20,20,20));
if(a==-&&b==-&&c==-) return ;
else if(a<=||b<=||c<=) printf("w(%d, %d, %d) = 1\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));
}
return ;
}
最新文章
- Session跟SessionFactory的线程安全与非安全
- PHP-----类与对象,成员方法,成员属性,构造方法,析构方法
- JavaScript学习小结(一)——JavaScript入门基础
- uva 11270 - Tiling Dominoes(插头dp)
- [转]设置MS Office Word for mac的默认显示比例
- spring DateUtils
- 两种代理模式(JDK和Cglib)实例
- 理解HTTPS
- 070、如何定制Calico 网络policy(2019-04-15 周一)
- spring mybatis整合
- mybatis百科-列映射类ResultMapping
- java框架之SpringCloud(4)-Ribbon&;Feign负载均衡
- 查看mysql执行的线程,并杀掉他
- V-rep学习笔记:机器人路径规划2
- 关于.babelrc中的stage-0,stage-1,stage-2,stage-3
- springMVC版本和jdk版本不匹配造成的问题
- CentOS下设置MySQL的root各种密码 总结
- Oracle常用sql语句。
- 镣铐之舞:美团安全工程师Black Hat USA演讲
- HDU 1104 Remainder (BFS求最小步数 打印路径)