bzoj2287【POJ Challenge】消失之物 缺一01背包
链接
bzoj
思路
分治solve(l,r,arr)表示缺少物品\([l,r]\)的dp数组arr。
然后solve(l,mid,arr)用右边的物品更新，solve(mid+1,r,arr)同理。
\(f(n)=2*f(\frac{n}{2})+(r-l+1)*m\)
复杂度为\(O(nmlog{n})\) 缺点最短路也是这样，用\(floyd\)
代码
#include <bits/stdc++.h>
using namespace std;
const int _=2e3+7;
int n,m,w[_],tmp[_<<2][_],ans[_],cnt;
void solve(int l,int r,int *f) {
if(l==r) {
for(int i=1;i<=m;++i) printf("%d",f[i]);puts("");
return;
}
int mid=(l+r)>>1,p=++cnt;
for(int i=0;i<=m;++i) tmp[p][i]=f[i];
for(int i=mid+1;i<=r;++i)
for(int j=m;j>=w[i];--j)
f[j]+=f[j-w[i]],f[j]%=10;
solve(l,mid,f);
for(int i=0;i<=m;++i) f[i]=tmp[p][i];
for(int i=l;i<=mid;++i)
for(int j=m;j>=w[i];--j)
f[j]+=f[j-w[i]],f[j]%=10;
solve(mid+1,r,f);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
tmp[0][0]=1,solve(1,n,tmp[0]);
return 0;
}
转载于:https://www.cnblogs.com/dsrdsr/p/11405969.html
相关资源：JAVA上百实例源码以及开源项目
