首页 > 代码库 > 【bzoj4800】: [Ceoi2015]Ice Hockey World Championship dfs
【bzoj4800】: [Ceoi2015]Ice Hockey World Championship dfs
【bzoj4800】: [Ceoi2015]Ice Hockey World Championship
N<=40所以如果直接dfs背包会TLE
考虑Meet-in-the-middle
如果把N个物品分成前后A B两段分别背包
分别在A B中可行的方案的花费记录在a b中
答案就是a[i]+b[j]<=M的个数
把a b排序 然后序列就是单调的了
两个指针扫一遍就好了
1 #include <cstdlib> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdio> 5 #include <algorithm> 6 using namespace std; 7 #define ll long long 8 9 10 ll n,m,mid,ans; 11 ll c[50],a[2][1100000],ca[2]; 12 13 void dfs(int p,int x,ll cost){ 14 if (cost>m) return; 15 if ((x>=mid && p==0) || (x>=n && p==1)){ 16 a[p][++ca[p]]=cost; 17 return; 18 } 19 dfs(p,x+1,cost+c[x+1]); 20 dfs(p,x+1,cost); 21 } 22 23 int main(){ 24 scanf("%lld%lld",&n,&m); 25 for (int i=1;i<=n;i++) scanf("%lld",&c[i]); 26 mid=n/2; 27 dfs(0,0,0); 28 dfs(1,mid,0); 29 sort(a[0]+1,a[0]+ca[0]+1); 30 sort(a[1]+1,a[1]+ca[1]+1); 31 for (int l=1,r=ca[1];l<=ca[0] && r>=1;ans+=r,l++) while (a[0][l]+a[1][r]>m) r--; 32 printf("%lld\n",ans); 33 return 0; 34 }
竟然有Rank4(2017.3.31)。。好快啊。。
【bzoj4800】: [Ceoi2015]Ice Hockey World Championship dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。