upc Get Strong 整体二分

题意很简单，就是分组背包。n只有20，队友想写dfs，我直呼内行。显然直接爆搜是不行的，复杂度高达$2^{40}$。反应了一会，发现这不是整体二分板子题嘛。。。$2^{40}$不行显然可以转换成两个$2^{20}$搜，让后两边体积拼凑起来。但是直接拼的话最坏也是$2^{40}$的，显然我们可以优化一下，枚举其中一个的体积，让后在另一个的 $[0,m-v[i]]$ 体积里面找最大价值就行了。找最大价值的话因为是从0开始，所以可以$O(N)$处理出来。比赛没带脑子写了个RMQ，爆内存爆的怀疑人生了。

#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std; void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); } typedef long long LL; typedef unsigned long long ULL; typedef pair<LL,LL> PII; const int N=110,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6; int n,m; int b[2048577]; LL mxx[2048577]; int v[N][N],w[N][N],s[N]; vector<PII>v1,v2; void dfs1(int u,LL _v,LL _w) { if(_v>m) return; if(u==n/2+1) { v1.pb({_v,_w}); return; } dfs1(u+1,_v,_w); LL v_=0,w_=0; for(int i=1;i<=s[u];i++) { v_+=1ll*v[u][i]; w_+=1ll*w[u][i]; dfs1(u+1,_v+v_,_w+w_); } } void dfs2(int u,LL _v,LL _w) { if(_v>m) return; if(u==n+1) { v2.pb({_v,_w}); return; } dfs2(u+1,_v,_w); LL v_=0,w_=0; for(int i=1;i<=s[u];i++) { v_+=1ll*v[u][i]; w_+=1ll*w[u][i]; dfs2(u+1,_v+v_,_w+w_); } } int main() { // ios::sync_with_stdio(false); // cin.tie(0); int _; scanf("%d",&_); for(int __=1;__<=_;__++) { v1.clear(); v2.clear(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&s[i]); for(int j=1;j<=s[i];j++) scanf("%d%d",&w[i][j],&v[i][j]); } dfs1(1,0,0); dfs2(n/2+1,0,0); sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); int l1=v1.size(),l2=v2.size(); LL ans=0; int n=l2; LL mx=v2[0].Y; for(int i=1;i<=n;i++) b[i]=v2[i-1].X,mx=max(mx,v2[i-1].Y),mxx[i]=mx; for(int i=0;i<l1;i++) { if(v1[i].X>m) break; int pos=upper_bound(b+1,b+1+l2,m-v1[i].X)-b; pos--; ans=max(ans,v1[i].Y+mxx[pos]); } printf("Case #%d: %lld\n",__,ans); } return 0; }