洛谷：P4799 [CEOI2015 Day2]世界冰球錦标賽（折半搜尋，剪枝搜素，省選/NOI-）

題目：

分析：這裡給的搜素題，總覺得不是很好。

終于遇到一道還不錯的。

本以為是基礎。

0優化代碼：

#include<bits/stdc++.h>
using namespace std;
long long A[50];
int m;
long long n;
long long ans=0;
void f(long long rest,int num)
{
 if(num==n) { ans++; return; }
 if(rest<A[num])
 {
  ans++;
  return;
 }
 f(rest,num+1);
 f(rest-A[num],num+1);
}
int main()
{
 cin>>m>>n;
 for(int i=0;i<m;i++) cin>>A[i];
 sort(A,A+m);
 f(n,0);
 cout<<ans;
}
           

相同的應該是可以優化的：

引入一個c—組合數，相同的可以極大的節省

代碼：

#include<bits/stdc++.h>
using namespace std;
int m;
long long n;
long long ans=0;
long long cc[41][41];
map<long long,int> mm; 
vector<long long> v;
void fc()
{
 for(int i=0;i<41;i++) cc[i][0]=1;
 for(int i=1;i<41;i++)
 for(int j=1;j<=i;j++) cc[i][j]=cc[i][j-1]*(i-j+1)/j;
} 
void f(long long rest,int num,long long b)
{
 if(num==v.size()) { ans+=b; return; }
 if(rest<v[num])
 {
  ans+=b;
  return;
 }
 f(rest,num+1,b);
 for(int i=1;i<=mm[v[num]];i++)
 {
  if(i*v[num]<=rest)
  {
   f(rest-i*v[num],num+1,b*cc[mm[v[num]]][i]);
  }
  else break;
 }
}
int main()
{
 //組合數cc的初始化 
 fc();
 //讀入 
 cin>>m>>n;
 for(int i=0;i<m;i++) 
 {
  long long c;
  cin>>c;
  if(mm[c]!=0) { mm[c]++; continue;  } 
  mm[c]++;
  v.push_back(c);
 }
 sort(v.begin(),v.end());
 f(n,0,1);
 cout<<ans;
}
           

竟然隻通過了40。

看來我小看了省選/NOI-的難度。

看題解：

折半搜尋：

我也沒了解為什麼能降低的比我的還多。

代碼：很容易了解，就是分成兩部分，用一個數組記錄所有可能的搜尋結果。然後用stl的搜尋函數進行合并。

代碼：

#include<bits/stdc++.h>
using namespace std;
long long A[50];
int m;
long long n;
long long ans=0;
long long suma[1<<21],sumb[1<<21];
void f1(long long sum,int l,int r,long long & cnt)
{
 if(sum>n) return;
 if(l>r)
 {
  suma[cnt]=sum;
  cnt++;
  return;
 }
 f1(sum+A[l],l+1,r,cnt);
 f1(sum,l+1,r,cnt);
}
void f2(long long sum,int l,int r,long long & cnt)
{
 if(sum>n) return;
 if(l>r)
 {
  sumb[cnt]=sum;
  cnt++;
  return;
 }
 f2(sum+A[l],l+1,r,cnt);
 f2(sum,l+1,r,cnt);
}
int main()
{
  cin>>m>>n;
  for(int i=0;i<m;i++) cin>>A[i];
  long long cnta=0;
  long long cntb=0;
  f1(0,0,m>>1,cnta);
  f2(0,(m>>1)+1,m-1,cntb);
  sort(suma,suma+cnta);
  //for(int i=0;i<cnta;i++) cout<<suma[i]<<' ';
  //cout<<endl;
  //for(int i=0;i<cntb;i++) cout<<sumb[i]<<' ';
  //cout<<endl;
  for(int i=0;i<cntb;i++)
  {
   ans+=upper_bound(suma,suma+cnta,n-sumb[i])-suma;
  }
  cout<<ans;
}