Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
为了不重复计算...贴上代码//有点像DP的备忘录...0ms AC... //存在巨大的时间浪费,主要是很多已经计算好的值又要被重新计算 //就像递归求Fibonacci数列一样,很多子递归进行很多次 //所以运用备忘录的形式,把已经计算好的数据放在数组里,递归之前先检查是否已经算好了 //算好了的话直接拿来用就行了 #include<iostream> using namespace std; int visit[21][21][21]; int r(int a,int b,int c) { if(a<=0||b<=0||c<=0)//注意啦...这个必须放前面...想象为什么吧 return visit[a][b][c]=1; if(a>20||b>20||c>20) return r(20,20,20); if(visit[a][b][c]) return visit[a][b][c]; if(a<b&&b<c) { return visit[a][b][c]=r(a, b, c-1) + r(a, b-1, c-1) - r(a, b-1, c); } return visit[a][b][c]=r(a-1, b, c)+r(a-1, b-1, c)+r(a-1, b, c-1)-r(a-1, b-1, c-1); } int main() { //freopen("1.txt","r",stdin); int a,b,c; while(scanf("%d%d%d",&a,&b,&c)) { memset(visit,0,sizeof(visit)); if(a==-1&&b==-1&&c==-1) return 0; printf("w(%d, %d, %d) = %d\n",a,b,c,r(a,b,c)); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator