原文链接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;
}