首页 > 代码库 > JZOJ.5264【NOIP2017模拟8.12】化学
JZOJ.5264【NOIP2017模拟8.12】化学
搜索。考虑到m很大，我们不得不从n下手，但240无法满足要求，我们可以采取折半搜索。
先搜前20个记录所有220的方案情况，再搜索后面20个，把全部方案数分别记录到两个数组里，从小到大排个序，然后用指针维护统计答案就可以了。
因为要两个情况所耗费的体力值不大于m，所以我们可以固定第一个数组的指针i，第二个数组指针j从大到小找到第一个加起来体力值小于m的，那剩下的都是符合要求的，对于下一个i，j就从当前位置继续往小的扫，因为这具有单调性。（二分也是个好方法）
折半搜索之所以能降低复杂度，就在于判断的时候运用了结果的某种性质从而提高速率，如果结果还是O(n2)暴力统计的话与直接搜索复杂度无多大差别。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<ctime> 8 using namespace std; 9 int n;10 long long m,w1[1<<21],w2[1<<21],ans,v[41];11 int main(){12 scanf("%d%lld",&n,&m);13 for (int i=1;i<=n;i++)14 scanf("%lld",&v[i]);15 w1[0]=0;w2[0]=0;16 int qwq=n/2;17 int qaq=(n+1)/2;18 for (int i=0;i<(1<<qwq);i++)19 for (int j=1;j<=qwq;j++)20 if ((i&(1<<(j-1)))==0) 21 w1[i|(1<<(j-1))]=w1[i]+v[j];22 for (int i=0;i<(1<<qaq);i++)23 for (int j=qwq+1;j<=n;j++)24 if ((i&(1<<(j-1-qwq)))==0) 25 w2[i|(1<<(j-1-qwq))]=w2[i]+v[j];26 sort(w1+1,w1+(1<<qwq));27 sort(w2+1,w2+(1<<qaq));28 ans=0;29 int r=(1<<qaq)-1;30 for (int i=0;i<(1<<qwq);i++){31 while ((w2[r]+w1[i]>m)&&(r>=0)) r--;32 ans+=r+1;33 }34 printf("%lld\n",ans);35 return 0;36 }
JZOJ.5264【NOIP2017模拟8.12】化学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。