[BZOJ 2287/POJ openjudge1009/Luogu P4141] 消失之物
题面:
传送门:http://poj.openjudge.cn/practice/1009/
Solution
DP+DP
首先,我们可以很轻松地求出所有物品都要的情况下的选择方案数,一个简单的满背包DP就好
即:f[i][j]表示前i个物品装满容量为j的背包的方案数.
转移也很简单 f[i][j]=f[i-1][j]+f[i-1][j-w[i]] (i:1~n,j:1~m) (即选和不选的问题)
初始化 f[i][0]=1 (i:[0~n]) (如果背包容量为0,无论如何都有且只有一种方案将其装满)
接下来,考虑用另一个dp来求解在某一物品不放下的方案数
设 g[i][j] 表示第i个物品不放入背包,装满容量为j的背包的方案数
转移为:
g[i][j] = f[n][j] ( j < w[i]) (即当背包容量小于所不放物品的大小时,那么其方案数必然为f[n][j],因为f[n][j]中的所有方案肯定取不到第i个)
= f[n][j] - g[i][j-w[i]]
i:1~n j:1~m
下面那个转移意思即是:
所有的方案总数 减去 包括第i项物品的方案数
因为g[i][j-w[i]]中的每一种情况再装入w[i]即可达到g[i][j]这个状态,而g[i][j]的定义是不装入i的方案数,所以说包括第i项物品的方案能且仅能从g[i][j-w[i]]转移过来
初始化:
g[i][0]=1 (i:[0~n])(背包容量为0时方案有且仅有啥都不要)
这样就可以口头AC了
但是,还有一个要注意的小地方
在%P的意义下, f[n][j]-g[i][j-w[i]]有可能为负数
负数取模的方法为 : (x % P + P)%P
然后就OK啦
Code
//Openjudge 1009:消失之物
//Apr,2ed,2018
//DP+DP
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=2000+100;
const int M=2000+100;
const int P=10;
char f[N][M],g[M];
int w[N],n,m;
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
w[i]=read(); f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j-w[i]>=0)
f[i][j]+=f[i-1][j-w[i]];
if(f[i][j]>=P) f[i][j]%=P;
} g[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j<w[i])
printf("%d",g[j]=f[n][j]);
else
printf("%d",g[j]=(f[n][j]-g[j-w[i]]+P)%P);
}
printf("\n");
}
return 0;
}
c++
后记
这种DP+DP的题目还是第一次写,写起来有一点点不熟练
看来我还是需要多学习一个
最新文章
- Linux内核分析--操作系统是如何工作的
- android 6.0权限处理
- Spring boot 1.3.5 RELEASE 官方文档中文翻译--目录
- Xcode7设置生成DSYM出现大量警告
- python多进程断点续传分片下载器
- 飘逸的python - 解决一个有限制的组合需求
- 用户登录之cookie信息安全一二事
- freemarker中值比较的写法
- 【Oracle】ORA-14400: 插入的分区关键字未映射到任何分区
- mongod.service: control process exited, code=exited status=1
- Windows 平台下局域网劫持测试工具 – EvilFoca
- Hbase记录-Hbase shell使用命令
- Struts2中的数据处理的三种方式对比(Action中三种作用域request,session,application对象)
- 微信小程序--bind 和catch区别
- 使用C#创建WCF服务控制台应用程序
- matlab与vs混合编程/matlab移植
- HDU 6201 transaction transaction transaction(树形DP)
- SRPG Studio 教程(一) 创建游戏及引用素材
- hdu 4715(打表)
- Linux系统中DHCP的配置