bzoj2287 消失之物 01背包

本文主要是介绍bzoj2287 消失之物 01背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj2287（权限题qwq）

一开始看错数据范围了……打了一个极为暴力（$O(n^{2}m)$）的暴力……暴力代码如下：

毒瘤代码1

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x) {if(x>9)	write(x/10);putchar(x%10+'0');
}
const int Size=2005;
namespace I_Love {int n,m,w[Size],dp[Size][Size];
void Kutori() {n=read();m=read();for(re i=1; i<=n; i++) {w[i]=read();}for(re i=1; i<=n; i++) {memset(dp,0,sizeof(dp));dp[0][0]=1;for(re j=1; j<=n; j++) {if(i==j) {continue;} else if(j==i+1) {memcpy(dp[j],dp[i-1],sizeof(dp[i-1]));for(re k=w[j]; k<=m; k++) {dp[j][k]=(dp[j][k]+dp[i-1][k-w[j]])%10;}} else {memcpy(dp[j],dp[j-1],sizeof(dp[j-1]));for(re k=w[j]; k<=m; k++) {dp[j][k]=(dp[j][k]+dp[j-1][k-w[j]])%10;}}}if(i==n) {for(re j=1; j<=m; j++) {putchar(dp[n-1][j]+'0');}} else {for(re j=1; j<=m; j++) {putchar(dp[n][j]+'0');}}putchar(10);}
}}
int main() {I_Love::Kutori();return 0;
}

这样的暴力显然会T到飞起，考虑怎样$O(nm)$解决：
这里让$dp[i][j]$表示用前$i$个物品填满容量为$j$的背包的方法数，$cnt[i][j]$表示用除第$i$种物品之外的所有物品填满容量为$j$的背包的方案数。
$dp[i][j]$显然珂以$O(nm)$大莉跑01背包，关键是怎样$O(nm)$搞出$cnt$数组。
发现直接求解$cnt[i][j]$是不珂取的（会变成$O(n^{2}m)$的暴力），所以考虑用$dp$来推出$cnt$。qwq
因为$cnt[i][j]$包含的条件是“不能用第$i$种物品”，所以从所有情况中去掉用了第$i$种物品的情况就珂以了qwq
不过注意当$j<w[i]$时，不用去掉情况qwq。
转移方程：$cnt[i][j]=dp[n][j]-cnt[i][j-w[i]]$（$cnt[i][j-w[i]]$表示先不选$i$，再强制选$i$）

毒瘤代码2

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x) {if(x>9)	write(x/10);putchar(x%10+'0');
}
const int Size=2005;
namespace I_Love {int n,m,w[Size];
int dp[Size][Size];
int cnt[Size][Size];
void Kutori() {n=read();m=read();for(re i=1; i<=n; i++) {w[i]=read();}dp[0][0]=1;for(re i=1; i<=n; i++) {memcpy(dp[i],dp[i-1],sizeof(dp[i-1]));for(re j=w[i]; j<=m; j++) {dp[i][j]=(dp[i][j]+dp[i-1][j-w[i]])%10;}}for(re i=1; i<=n; i++) {memcpy(cnt[i],dp[n],w[i]<<2);for(re j=w[i]; j<=m; j++) {cnt[i][j]=(dp[n][j]-cnt[i][j-w[i]]+10)%10;}for(re j=1; j<=m; j++) {putchar(cnt[i][j]+'0');}putchar(10);}
}}
int main() {I_Love::Kutori();return 0;
}

闲着没事的zyd发现$dp$数组和$cnt$数组都珂以滚掉一维，所以出现了下面的代码：

毒瘤代码3

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x) {if(x>9)	write(x/10);putchar(x%10+'0');
}
const int Size=2005;
namespace I_Love {int n,m,w[Size],dp[Size],cnt[Size];
void Kutori() {n=read();m=read();for(re i=1; i<=n; i++)	w[i]=read();dp[0]=1;for(re i=1; i<=n; i++) {for(re j=m; j>=w[i]; j--) {dp[j]=(dp[j]+dp[j-w[i]])%10;}}for(re i=1; i<=n; i++) {for(re j=0; j<=m; j++) {if(j<w[i]) {cnt[j]=dp[j];} else {cnt[j]=(dp[j]-cnt[j-w[i]]+10)%10;}}for(re j=1; j<=m; j++) {putchar(cnt[j]+'0');}putchar(10);}
}}
int main() {I_Love::Kutori();return 0;
}

这篇关于bzoj2287 消失之物 01背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---