BZOJ2287 【POJ Challenge】消失之物 动态规划 分治

时间:2021-08-19 08:38:49

原文链接http://www.cnblogs.com/zhouzhendong/p/8684027.html

题目传送门 - BZOJ2287

题意

  有$n$个物品,第$i$个物品的体积为$w_i$。

  令$cnt_{i,j}$表示不取第$i$个物品,占用$j$体积的方案总数。

  每一个物品只能取或者不取。

  让你对于每一个$i,j(1\leq i\leq n,1\leq j\leq m)$输出$cnt_{i,j}$。

  $n,m\leq 2\times 10^3$

题解

  这题有两种做法,时间复杂度不同,但是跑出来差不多,嘻嘻。

  $\Large Solution\ 1:$

  这个是经典的分治背包问题。第$i$个物品的出现时间为[1,i)U(i,n]。

  然后你会发现这个就是上一题BZOJ4025的弱化版。只是把并查集的一系列操作改成了$O(m)$背包DP而已。

  具体不再赘述,自行感受BZOJ4025的做法。

  时间复杂度$O(n^2\log n)$。

  $\Large Solution\ 2:$

  动态规划。

  首先处理出$f_n$表示没有任何限制搞01背包占用$n$体积的方案总数。

  考虑得到$cnt_{i,j}$。

  接下来分两种情况讨论。

  $j<w_i\Rightarrow cnt_{i,j}=f_j$:显然$f_j$的方案中不可能拿第$i$个物品啊。所以直接等于啊。

  $j\geq w_i\Rightarrow cnt_{i,j}=f_j-cnt_{i,j-w_i}$:考虑到$f_j$的方案中会有拿了第$i$个物品的情况,所以我们只要考虑减掉拿了第$i$个物品的情况。其他物品所占用的容量显然为$j-w_i$的。但是第$i$个物品只能拿一次啊,所以以后就不能拿了,所以是$cnt_{i,j-w_i}$。

  时间复杂度$O(n^2)$。

  然而,实际上跑出来差不多。

2679062 zhouzhendong 2287 Accepted 17008 kb 388 ms C++/Edit 610 B 2018-03-31 20:01:27
2679058 zhouzhendong 2287 Accepted 17004 kb 452 ms C++/Edit 942 B 2018-03-31 19:56:48

  下面的那个是分治的耗时,上面的那个是直接DP。

代码

分治

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
vector <int> x,y;
int n,m,w[N],cnt[N][N];
void solve(int L,int R,vector <int> x,vector <int> &y){
vector <int> z;
z.clear();
for (int i=0;i<y.size();i++){
int id=y[i];
if (L<=id&&id<=R){
z.push_back(id);
continue;
}
for (int j=m-w[id];j>=0;j--)
x[j+w[id]]=(x[j+w[id]]+x[j])%10;
}
if (L==R){
for (int i=0;i<=m;i++)
cnt[L][i]=x[i];
return;
}
int mid=(L+R)>>1;
solve(L,mid,x,z);
solve(mid+1,R,x,z);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&w[i]);
x.clear(),y.clear();
x.push_back(1);
for (int i=1;i<=m;i++)
x.push_back(0);
for (int i=1;i<=n;i++)
y.push_back(i);
solve(1,n,x,y);
for (int i=1;i<=n;i++,puts(""))
for (int j=1;j<=m;j++)
printf("%d",cnt[i][j]);
return 0;
}

  

DP

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m,w[N],f[N],cnt[N][N];
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&w[i]);
memset(f,0,sizeof f);
f[0]=1;
for (int i=1;i<=n;i++)
for (int j=m-w[i];j>=0;j--)
f[j+w[i]]=(f[j+w[i]]+f[j])%10;
for (int i=1;i<=n;i++){
for (int j=0;j<w[i];j++)
cnt[i][j]=f[j];
for (int j=w[i];j<=m;j++)
cnt[i][j]=(f[j]-cnt[i][j-w[i]]+10)%10;
}
for (int i=1;i<=n;i++,puts(""))
for (int j=1;j<=m;j++)
printf("%d",cnt[i][j]);
return 0;
}