今天是在学习折半搜索。
洛谷P4799
1.直接搜，比较简单的搜索，但只能过前两个子任务。
#include<iostream>
#include<algorithm>
using namespace std;
int n;
long long m;
long long a[50];
bool cmp(long long x,long long y){
return x<y;
}
long long dfs(int x,long long y){
if(x==n){
return 1;
}
long long ans=1;
for(int i=x+1;a[i]+y<=m&&i<=n;i++){
ans=ans+dfs(i,y+a[i]);
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
cout<<dfs(0,0);
return 0;
}
2.背包dp，可过1,3两个子任务。
#include<iostream>
using namespace std;
int n;
long long m;
long long a[1000010];
long long f[1000010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
f[j]+=f[j-a[i]];
}
}
long long ans=0;
for(int j=0;j<=m;j++){
ans+=f[j];
}
cout<<ans;
return 0;
}
3但第二个子任务背包dp空间不可行，考虑day1的对dp的多余状态的优化，unordered_map，可过1,2,3三个子任务。
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
int n;
long long m;
long long a[50];
long long dui[10000010];
long long b[10000010];
int cnt2=0;
long long c[10000010];
int cnt=0;
bool cmp(long long x,long long y){
return x<y;
}
bool cnp(long long x,long long y){
return x>y;
}
unordered_map<long long ,long long> f;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,cnp);
f[0]=1;
dui[++cnt]=0;
for(int i=1;i<=n;i++){
for(int j=cnt;j>=1;j--){
c[cnt-j+1]=dui[j];
}
int l=0,r=cnt;
while(l<r){
int mid=(l+r+1)/2;
if(a[i]+dui[mid]>m){
r=mid-1;
}
else{
l=mid;
}
}
cnt2=0;
for(int j=l;j>=1;j--){
if(f[dui[j]+a[i]]==0){
b[++cnt2]=dui[j]+a[i];
}
f[dui[j]+a[i]]+=f[dui[j]];
}
int cnt1=cnt;
int j=cnt1,k=cnt2;
cnt=0;
while(j>=1||k>=1){
if(j<1){
dui[++cnt]=b[k];
k--;
continue;
}
if(k<1){
dui[++cnt]=c[j];
j--;
continue;
}
if(c[j]<b[k]){
dui[++cnt]=c[j];
j--;
}
else{
dui[++cnt]=b[k];
k--;
}
}
}
long long ans=0;
for(int i=1;i<=cnt;i++){
ans+=f[dui[i]];
}
cout<<ans;
return 0;
}
4.考虑我们只需要知道总方案数是多少，并不需要知道各个状态的方案数是多少，第四个子任务n<=40，将它折半，就是两个第二个子任务，每个第二个子任务的状态数最多是2^n个，这样对两个第二个子任务分别按状态大小排序，前缀和加双指针，在第二个子任务中用map记录每个状态的方案数。
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
unsigned int n;
unsigned long long m;
unsigned long long a[50];
unordered_map<unsigned long long,unsigned long long>mp1;
unordered_map<unsigned long long,unsigned long long>mp2;
unsigned long long dui1[1100010];
unsigned int cnt1=0;
unsigned long long dui2[1100010];
unsigned int cnt2=0;
inline void dfs1(unsigned int x,unsigned long long y){
if(x==n){
return ;
}
for(int i=x+1;a[i]+y<=m&&i<=n;i++){
if(mp1[y+a[i]]==0){
dui1[++cnt1]=y+a[i];
}
mp1[y+a[i]]++;
if(y+a[i]<m)dfs1(i,y+a[i]);
}
}
inline void dfs2(unsigned int x,unsigned long long y){
if(x==n){
return ;
}
for(int i=x+1;a[i]+y<=m&&i<=n;i++){
if(mp2[y+a[i]]==0){
dui2[++cnt2]=y+a[i];
}
mp2[y+a[i]]++;
if(y+a[i]<m)dfs2(i,y+a[i]);
}
}
inline bool cmp(unsigned long long x,unsigned long long y){
return x<y;
}
unsigned long long qian[1100010];
int main(){
cin>>n>>m;
for(unsigned int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
dui2[++cnt2]=0;
mp2[0]=1;
dfs2(n/2,0);
n/=2;
dui1[++cnt1]=0;
mp1[0]=1;
dfs1(0,0);
sort(dui1+1,dui1+cnt1+1,cmp);
sort(dui2+1,dui2+cnt2+1,cmp);
for(unsigned int j=1;j<=cnt2;j++){
qian[j]=qian[j-1]+mp2[dui2[j]];
}
int j=cnt2;
unsigned long long ans=0;
for(unsigned int i=1;i<=cnt1&&j>0;i++){
while(j>0&&dui2[j]+dui1[i]>m){
j--;
}
if(j>0){
ans+=mp1[dui1[i]]*qian[j];
}
}
cout<<ans;
return 0;
}