codeforces E - Anya and Cubes 分块处理暴力搜索-白红宇

codeforces E - Anya and Cubes 分块处理暴力搜索

阅读量：5299 次

发布时间：2019-06-14

本文共 1175 字，大约阅读时间需要 3 分钟。

说的是给了n个立方体，立方体从1标号到n，每个立方体上有一个数字，你有 k 个机会使得其中 k个数位他们自己的阶乘，（自然使用可以少于k次机会，每个立方体最多被使用1次），那么求出你从这n个立方体重选出任意个立方体使得他们的和为S

n<25

可以知道直接使用n去枚举自然受不了，我们将n个数字分为两部分来算，前面n/2个数字我们枚举他们使用j次可以得到的数，然后后面的n-n/2个数再次使用这个方法，直接在dfs枚举的时候进行判断S-s 在前一个钟是否出现过，出现过就加起来。分块处理

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
         5 #include
         
           6 using namespace std; 7 typedef long long LL; 8 map
          
           mp[30]; 9 LL A[30];10 LL dp[30];11 LL time[1000000];12 int n,K;13 LL S,ans;14 void dfs(int p, int k, LL s){15 if(p==n/2){16 mp[k][s]++;17 }else{18 dfs(p+1,k,s);19 if(s+A[p]<=S)dfs(p+1,k,s+A[p]);20 if(k+1<=K && A[p]<=18 && s+dp[A[p]] <=S ) dfs(p+1,k+1,s+dp[A[p]]);21 }22 }23 void dfs1(int p, int k, LL s){24 if(p==n){25 for(int i =0; i+k<=K; i++)26 if(mp[i].count(S-s)>0) ans+=mp[i][S-s];27 }else{28 dfs1(p+1,k,s);29 if(s+A[p]<=S) dfs1(p+1,k,s+A[p]);30 if(k+1<=K && A[p]<=18 && s+dp[A[p]]<=S) dfs1(p+1,k+1,s+dp[A[p]]);31 }32 }33 int main()34 {35 36 37 dp[0]=1;38 for(LL i=1; i<=18; i++) dp[i]=dp[i-1]*i;39 ans=0;40 scanf("%d%d%I64d",&n,&K,&S);41 for(int i=0; i

转载于:https://www.cnblogs.com/Opaser/p/4381974.html

你可能感兴趣的文章