UVA 10564 - Paths through the Hourglass

题目链接~~>

做题感悟：这题上来就暴力了一下，就过可想而知，想用过记忆划搜索但是就是为什么没想到增加一维呢??

解题思路：

                  因为到达每种状态都有许多的可以组成的值，so ~ 可以开三维的数组即：dp[ i ] [ j ] [ s ]  代表第 i 行 第 j 个 组合成 s 有多少种方法。用记忆化搜索比较好写，注意处理边界。还有一点很坑，路径条数要用 long long int 保存，因为这个错了两次。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MY = 40 + 10 ;
     
    
   

    

     

    
    

     

      const int MX = 500 + 10 ;
     
    
   

    

     

    
    

     

      INT n,m,tot ;
     
    
   

    

     

    
    

     

      INT dp[MY][MY][MX],g[MY][MY] ;
     
    
   

    

     

    
    

     

      INT dy[4]={-1,0,0,1} ;
     
    
   

    

     

    
    

     

      char s[5]={'L','R','L','R'} ;
     
    
   

    

     

    
    

     

      INT DP(INT x,INT y,INT S) // 记忆化搜索
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT st=0,ed=0 ;
     
    
   

    

     

    
    

     
 if(dp[x][y][S]!=-1)
     
    
   

    

     

    
    

     
 return dp[x][y][S] ;
     
    
   

    

     

    
    

     

       INT& ans = dp[x][y][S] ;
     
    
   

    

     

    
    

     
 if(x<=m-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       st=0 ;ed=2 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       st=2 ; ed=4 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       INT mx=0 ;
     
    
   

    

     

    
    

     
 for(INT j=st ; j<ed ;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       INT sx=x+1 ;
     
    
   

    

     

    
    

     

       INT sy=y+dy[j] ;
     
    
   

    

     

    
    

     
 if(S>=g[sx][sy]&&g[sx][sy]!=-1)
     
    
   

    

     

    
    

     

       mx+=DP(sx,sy,S-g[sx][sy]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans=mx ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void input() // 输入处理
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       n=m*2-1 ;
     
    
   

    

     

    
    

     
 memset(g,-1,sizeof(g)) ;
     
    
   

    

     

    
    

     
 memset(dp,-1,sizeof(dp)) ;
     
    
   

    

     

    
    

     
 for(INT i=m ;i>=2 ;i--)
     
    
   

    

     

    
    

     
 for(INT j=1 ;j<=i ;j++)
     
    
   

    

     

    
    

     
 scanf("%lld",&g[m-i+1][j]) ;
     
    
   

    

     

    
    

     
 for(INT i=m,j=1 ;i<=n ;i++,j++)
     
    
   

    

     

    
    

     
 for(INT k=1 ;k<=j ;k++)
     
    
   

    

     

    
    

     
 scanf("%lld",&g[i][k]) ;
     
    
   

    

     

    
    

     
 for(INT i=1 ;i<=m ;i++)
     
    
   

    

     

    
    

     

       dp[n][i][0]=1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void print(INT x,INT y,INT S) // 递归输出
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT st=0,ed=0 ;
     
    
   

    

     

    
    

     
 if(x<=m-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       st=0 ;ed=2 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       st=2 ; ed=4 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(INT i=st ;i<ed ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       INT sx=x+1 ;
     
    
   

    

     

    
    

     

       INT sy=y+dy[i] ;
     
    
   

    

     

    
    

     
 if(g[sx][sy]!=-1&&S>=g[sx][sy]&&dp[sx][sy][S-g[sx][sy]]>=1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cout<<s[i]  ;
     
    
   

    

     

    
    

     

       print(sx,sy,S-g[sx][sy]) ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(scanf("%d%d",&m,&tot),m+tot)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     

       INT best=0 ;
     
    
   

    

     

    
    

     
 for(INT i=1 ;i<=m ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(tot>=g[1][i])
     
    
   

    

     

    
    

     

       dp[1][i][tot]=DP(1,i,tot-g[1][i]) ;
     
    
   

    

     

    
    

     
 if(dp[1][i][tot]>0)
     
    
   

    

     

    
    

     

       best+=dp[1][i][tot] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<best<<endl ;
     
    
   

    

     

    
    

     
 if(best)
     
    
   

    

     

    
    

     
 for(INT i=1 ;i<=m ;i++)
     
    
   

    

     

    
    

     
 if(dp[1][i][tot]>=1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cout<<i-1<<" " ;
     
    
   

    

     

    
    

     

       print(1,i,tot-g[1][i]) ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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