2287. 【POJ Challenge】消失之物

這題的思想和P4564 [CTSC2018]假面優化的思想一樣，應該反過來說，假面那個題應該是借鑒這題的思路。

顯然不能枚舉每個物品消失$O(n)$，然后跑背包$O(nm)$

預處理dp
$f_j$表示$n$個物品裝滿體積為$j$的背包的方案數。
$g_{i,j}$表示除了第$i$個物品其他$n?1$個物品裝滿體積為$j$的背包的方案數。

顯然$f_j=g_{i,j}+g_{i,j?v_i}$，于是$g_{i,j}=f_j+g_{i,j?v_i}$

預處理$f_j$后我們可以$O(n)$遞推$g_{i,j}$（g數組第一維顯然沒有必要）

#include<cstring> #include<iostream> using namespace std; constexpr int N=2010; int n,m; int f[N],g[N]; int v[N]; int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i];f[0]=1;for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--)f[j]=(f[j]+f[j-v[i]])%10;for(int i=1;i<=n;i++){memset(g,0,sizeof g);for(int j=0;j<v[i];j++) g[j]=f[j];for(int j=v[i];j<=m;j++) g[j]=((f[j]-g[j-v[i]])%10+10)%10;for(int j=1;j<=m;j++) cout<<g[j];cout<<'\n';}return 0; }

上面的trick非常巧妙，但是下面有一種方法，不如說是一種框架——分治 更值得去學習掌握。

寒假訓練的時候就有一個分治的問題
XVIII Open Cup named after E.V. Pankratiev. Eastern Grand Prix K. King and ICPC不過現在沒有oj測評沒法補了~~就補個這個題吧（雖然分治里面不一樣，不過都是分治的框架）

LinnBlanc題解分治背包

//O(nmlogn) #include<cstring> #include<iostream> using namespace std; constexpr int N=2010; int n,m; int v[N],f[15][N]; void solve(int u,int l,int r) {if(l==r) {for(int j=1;j<=m;j++) cout<<f[u-1][j];cout<<'\n';return;}int mid=l+r>>1;for(int j=0;j<=m;j++) f[u][j]=f[u-1][j];for(int i=mid+1;i<=r;i++)for(int j=m;j>=v[i];j--)f[u][j]+=f[u][j-v[i]],f[u][j]%=10;solve(u+1,l,mid);for(int j=0;j<=m;j++) f[u][j]=f[u-1][j];for(int i=l;i<=mid;i++)for(int j=m;j>=v[i];j--)f[u][j]+=f[u][j-v[i]],f[u][j]%=10;solve(u+1,mid+1,r);} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i];f[0][0]=1;solve(1,1,n);return 0; }

upd:2021/3/8 下面題目效仿上面分治的做法即可

P4095 [HEOI2013]Eden 的新背包問題

同樣可能少一個物品，按照上面分治的思路預處理少某個物品的背包即可。

多重背包->二進制優化（單調隊列不會，難寫）

時間復雜度$O(nm{\log }^{2}n+q)$

#include<bits/stdc++.h> using namespace std; using ll=long long; constexpr int N=1010; int n,m,q; int v[N*10],w[N*10],cnt; int L[N],R[N]; int f[15][N],ans[N][N]; void update(int u,int l,int r) {for(int i=L[l];i<=R[r];i++)for(int j=m;j>=v[i];j--)f[u][j]=max(f[u][j],f[u][j-v[i]]+w[i]); } void solve(int u,int l,int r) {if(l==r) return memcpy(ans[l],f[u-1],sizeof(ans[l])),void();int mid=l+r>>1;memcpy(f[u],f[u-1],sizeof(f[u]));update(u,mid+1,r);solve(u+1,l,mid);memcpy(f[u],f[u-1],sizeof(f[u]));update(u,l,mid);solve(u+1,mid+1,r); }int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;m=1000;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;L[i]=cnt+1;int k=1;while(k<=c){v[++cnt]=k*a;w[cnt]=k*b;c-=k;k*=2;}if(c) {v[++cnt]=c*a;w[cnt]=c*b;}R[i]=cnt;}solve(1,1,n);cin>>q;while(q--){int d,e;cin>>d>>e;++d;cout<<ans[d][e]<<'\n';}return 0; }

總結

以上是生活随笔為你收集整理的2287. 【POJ Challenge】消失之物（数组递推\分治优化背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。