洛谷P1118 [USACO06FEB]数字三角形Backward Digit Su…     搜索

这题我们发现每一个位置的加权就是 杨辉三角 yh[ n ][ i ]

然后我们就可以求 n! 暴力 ，但是会 TLE 额 好像是会T 因为12! 已经 4亿了

然后我们加一个强力剪枝 如果当前求出来的 s 已经大于 sum了，因为没有负的加

权，也就是说这一路是没有用了的，在继续搜下去也不能更新答案了，那么就直接退出 。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ;10 11 int n,sum ;12 int ans[13],yh[13][13] ;13 bool finished ;14 bool used[13] ;15 16 inline void dfs(int p,int s)17 {18 if(p>n) 19 {20 if(s==sum) 21 {22 finished = 1 ;23 for(int i=1;i<=n;i++) printf("%d ",ans[ i ]) ;24 exit(0) ;25 }26 return ;27 }28 for(int i=1;i<=n;i++) 29 {30 if(!used[ i ]) 31 {32 if(s+yh[n][p]*i>sum) continue ; //剪枝 即不能更新答案了 33 ans[ p ] = i ; 34 used[ i ] = 1 ;35 dfs(p+1,s+yh[n][p]*i) ;36 used[ i ] = 0 ;37 }38 } 39 }40 41 int main() 42 {43 scanf("%d%d",&n,&sum) ;44 yh[1][1] = 1 ;45 for(int i=2;i<=n;i++) 46 for(int j=1;j<=i;j++) 47 yh[ i ][ j ] = yh[ i-1 ][ j-1 ]+yh[ i-1 ][ j ] ;48 49 dfs(1,0) ;50 51 return 0 ;52 }