学步园

记忆化搜索！

#include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> using namespace std;<br /> int dp[21][21][21];<br /> int w(int a,int b,int c)<br /> {<br /> if(a<=0||b<=0||c<=0)<br /> {<br /> dp[a][b][c]=1;<br /> return 1;<br /> }<br /> if(dp[a][b][c]!=0)<br /> return dp[a][b][c];<br /> if(a<b&&b<c)<br /> {<br /> dp[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);<br /> return dp[a][b][c];<br /> }<br /> else<br /> {<br /> dp[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);<br /> return dp[a][b][c];<br /> }<br /> }<br /> int main()<br /> {<br /> int a,b,c,x,y,z;<br /> while(cin>>a>>b>>c)<br /> {<br /> if(a==-1&&c==-1&&b==-1) break;<br /> if(a<=0||b<=0||c<=0 )<br /> printf("w(%d, %d, %d) = %d/n",a,b,c,1);<br /> else<br /> {<br /> x=a;y=b;z=c;<br /> if(a>20||b>20||c>20)<br /> {<br /> x=20;y=20;z=20;<br /> }<br /> memset(dp,0,sizeof(0));<br /> printf("w(%d, %d, %d) = %d/n",a,b,c,w(x,y,z));<br /> }<br /> }<br /> return 0;<br /> }