HDU 1331 Function Run Fun

题目链接~~>

做题感悟：这题真无语明明很简单！！

解题思路：记忆化搜索 or  递推。

代码（记忆化搜索）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      const int INF = -99999999 ;
     
    
   

    

     

    
    

     

      const int MX= 105 ;
     
    
   

    

     

    
    

     

      int dp[MX][MX][MX] ;
     
    
   

    

     

    
    

     

      int dfs(int a,int b,int c)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 // 注意不能在这判断if(dp[a][b][c]) return dp[a][b][c] ;
     
    
   

    

     

    
    

     
 // 因为输入的 a b c 可能为负数。
     
    
   

    

     

    
    

     
 if(a<=0||b<=0||c<=0)
     
    
   

    

     

    
    

     
 return  1 ;
     
    
   

    

     

    
    

     
 else if(a>20||b>20||c>20)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!dp[a][b][c])
     
    
   

    

     

    
    

     

       dp[a][b][c]=dfs(20,20,20) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(a<b&&b<c)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!dp[a][b][c])
     
    
   

    

     

    
    

     

       dp[a][b][c]=dfs(a,b,c-1)+dfs(a,b-1,c)-dfs(a,b-1,c) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else  if(!dp[a][b][c])
     
    
   

    

     

    
    

     

       dp[a][b][c]=dfs(a-1,b,c)+dfs(a-1,b-1,c)+dfs(a-1,b,c-1)-dfs(a-1,b-1,c-1) ;
     
    
   

    

     

    
    

     
 return dp[a][b][c] ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int a,b,c ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d%d",&a,&b,&c)&&(a!=-1||b!=-1||c!=-1))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(dp,0,sizeof(dp)) ;
     
    
   

    

     

    
    

     
 printf("w(%d, %d, %d) = %d\n",a,b,c,dfs(a,b,c)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（递推）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      const int INF = -99999999 ;
     
    
   

    

     

    
    

     

      const int MX= 25 ;
     
    
   

    

     

    
    

     

      int dp[MX][MX][MX] ;
     
    
   

    

     

    
    

     

      void init()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<=20 ;i++)
     
    
   

    

     

    
    

     
 for(int j=0 ;j<=20 ;j++)
     
    
   

    

     

    
    

     
 for(int k=0 ;k<=20 ;k++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(i<=0||j<=0||k<=0)
     
    
   

    

     

    
    

     

       dp[i][j][k]=1 ;
     
    
   

    

     

    
    

     
 else if(i<j&&j<k)
     
    
   

    

     

    
    

     

       dp[i][j][k]=dp[i][j][k-1]+dp[i][j-1][k-1]-dp[i][j-1][k] ;
     
    
   

    

     

    
    

     
 else dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k]+dp[i-1][j][k-1]-dp[i-1][j-1][k-1] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

     
 int a,b,c,ans ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d%d",&a,&b,&c)&&(a!=-1||b!=-1||c!=-1))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(a<=0||b<=0||c<=0)
     
    
   

    

     

    
    

     

       ans=1 ;
     
    
   

    

     

    
    

     
 else if(a>20||b>20||c>20)
     
    
   

    

     

    
    

     

       ans=dp[20][20][20] ;
     
    
   

    

     

    
    

     
 else if(a<b&&b<c)
     
    
   

    

     

    
    

     

       ans=dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c] ;
     
    
   

    

     

    
    

     
 else ans=dp[a-1][b][c]+dp[a-1][b-1][c]+dp[a-1][b][c-1]-dp[a-1][b-1][c-1] ;
     
    
   

    

     

    
    

     
 printf("w(%d, %d, %d) = %d\n",a,b,c,ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/20951907