TOKIOMARINE2020 D. Knapsack Queries on a tree
Difficulty:2158
問題文
#TOKIOM #TOK
#半分全列挙 #ナップザックDP ##bit全探索
問題
解法
浅いところでは愚直なDP、深いところではさっきのDPの結果+bit全探索をする。半分全列挙のような形になる。
実装
提出コード
code:cpp
bool solve(){
LL(n);
vector<ll>v(n+1),w(n+1);
rep(i,1,n+1){
cin >> vi >> wi;
}
vector<vector<pair<ll,ll>>>queries(n+1);
LL(q);
rep(i,q){
LL(v,L);
queriesv.push_back({L,i});
}
ll X = 100005;
vector<ll>noww(1),nowv(1),dp(X,-INF),ans(q);
auto&ndp = dp;
dp0 = 0;
vector<vector<ll>>dps(1,dp);
[DFS(&(auto&&g,ll pos,ll depth)->void{
if(pos>n)return;
if(depth<9){
auto pre = ndp;
for(int i = X-1;i>=wpos;i--){
chmax(ndpi,ndp[i-wpos]+vpos);
}
rep(i,X){
if(i)chmax(ndpi,ndpi-1);
}
for(autoL,ind:queriespos){
ansind = ndpL;
}
g(g,pos*2,depth+1);
g(g,pos*2+1,depth+1);
ndp = pre;
}
else{
ll sz = noww.size();
rep(i,sz){
noww.push_back(nowwi+wpos);
nowv.push_back(nowvi+vpos);
}
rep(i,sz*2){
for(autoL,ind:queriespos){
if(L-nowwi>=0)chmax(ansind,ndp[L-nowwi]+nowvi);
}
}
g(g,pos*2,depth+1);
g(g,pos*2+1,depth+1);
rep(i,sz){
noww.pop_back();
nowv.pop_back();
}
}
})]{DFS(DFS,1,0);}();
rep(i,q){
O(ansi);
}
return false;
}