superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1168 - Function Run Fun

Posted on 2008-04-11 18:46 superman 阅读(365) 评论(1)  编辑 收藏 引用 所属分类: ZOJ
I can't stand the problem.
TLE many times just because of using cin/cout :(
 1 /* Accepted 1168 C++ 00:00.21 472K */
 2 #include <stdio.h>
 3 
 4 int f[21][21][21];
 5 int w(int a, int b, int c)
 6 {
 7     if(a <= 0 || b <= 0 || c <= 0)
 8         return 1;
 9     
10     if(f[a][b][c])
11         return f[a][b][c];    
12     
13     if(a < b && b < c)
14         return f[a][b][c] = w(a, b, c-1+ w(a, b-1, c-1- w(a, b-1, c);
15     return 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);
16 }
17 
18 int main()
19 {
20     int a, b, c;
21     while(scanf("%d %d %d"&a, &b, &c) != EOF)
22     {
23         if(a == -1 && b == -1 && c == -1)
24             break;
25         
26         printf("w(%d, %d, %d) = ", a, b, c);
27         if(a <= 0 || b <= 0 || c <= 0)
28             printf("1\n");
29         else
30         {
31             if(a > 20 || b > 20 || c > 20)
32                 a = 20, b = 20, c = 20;
33             printf("%d\n", w(a, b, c));
34         }
35     }
36     
37     return 0;
38 }
39 

Feedback

# re: ZOJ 1168 - Function Run Fun  回复  更多评论   

2008-10-08 16:41 by kk
//更大的问题在于你没更多的保存中间值 ~_~

#include<iostream> //为避免无限的或大量的重复递归,,怎么办??,数组模拟

using namespace std;

const int N=100;
int f[N][N][N];

int recur(int a,int b,int c){

if(a<=0 || b<=0 || c<=0){
f[a][b][c]=1;
}
else if(a>20 || b>20 || c>20){
f[a][b][c]=recur(20,20,20);

}
else if(a<b && b<c){
if(f[a][b][c-1] == 0 )
f[a][b][c-1]=recur(a,b,c-1);
if(f[a][b-1][c-1]== 0)
f[a][b-1][c-1]=recur(a,b-1,c-1);
if(f[a][b-1][c] == 0 )
f[a][b-1][c]=recur(a,b-1,c);
f[a][b][c]=f[a][b][c-1]+f[a][b-1][c-1]-f[a][b-1][c];

}
else{
if(f[a-1][b][c] == 0)
f[a-1][b][c]=recur(a-1,b,c);
if(f[a-1][b][c-1] == 0)
f[a-1][b][c-1]=recur(a-1,b,c-1);
if(f[a-1][b-1][c] == 0)
f[a-1][b-1][c]=recur(a-1,b-1,c);
if(f[a-1][b-1][c-1]==0)
f[a-1][b-1][c-1]=recur(a-1,b-1,c-1);
f[a][b][c]=f[a-1][b][c]+f[a-1][b][c-1]+f[a-1][b-1][c]-f[a-1][b-1][c-1];
}

return f[a][b][c];

}

int main()
{

int a,b,c;

//cout<<"输入3个数: "<<endl;

while(cin>>a>>b>>c) {
//memset(f,0,sizeof(f));//写这个就超时。。。

if(a==-1 && b==-1 && c==-1) break;

if(a<=0 || b<=0 || c<=0)
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<1<<endl;

else
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<recur(a,b,c)<<endl;
}

return 0;

}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理