BZOJ2287: 【POJ Challenge】消失之物(背包dp)
2018-09-05 07:43:13来源:博客园 阅读 ()
题意
ftiasch 有 N 个物品, 体积分别是 W1, W2, ..., WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包,有几种方法呢?” -- 这是经典的问题了。她把答案记为 Count(i, x) ,想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。
Sol
Orz hzwer
这题可能有三种做法吧。。
第一种是分治背包
第二种是NTT优化暴力
第三种是$O(nm)$的神仙dp
这里只说一下第三种
首先设$f[i][j]$表示前$i$个物品选了$j$个,然后就是裸的完全背包
设$cnt[i][x]$表示答案
考虑这玩意儿怎么转移
- $cnt[i][0] = 1$
- 若$j \le w[i]$,$cnt[i][j] = f[n][j]$
- 若$j \geqslant w[i]$,$cnt[i][j] = f[n][j] - cnt[i][j - w[i]]$
第三个的转移非常神仙,反正我是没想出来,我们考虑用总的方案数减去用了改物品的方案数,我们发现直接算不是很好算,然后补集转化一下,用了物品$i$,体积为$j$,那么其他物品的体积为$j - w[i]$,这里的其他物品,也就是不用$i$的情况,也就是原来的$cnt$数组!!好神仙啊qwq
#include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<cmath> //#define int long long #define Pair pair<int, int> #define fi first #define se second #define MP(x, y) make_pair(x, y) using namespace std; const int MAXN = 1e6 + 10, mod = 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; int w[MAXN], f[2001][2001], cnt[2001][2001]; 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]) %= mod;//不装 if(j >= w[i]) (f[i][j] += f[i - 1][j - w[i]]) %= mod; } } for(int i = 1; i <= N; i++) { cnt[i][0] = 1; for(int j = 1; j <= M; j++) { if(j < w[i]) cnt[i][j] = f[N][j] % mod; else cnt[i][j] = (f[N][j] - cnt[i][j - w[i]] + mod) % mod; } } for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= M; j++) printf("%d", cnt[i][j] % mod); return 0; } /* 3 2 1 1 2 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:采药---背包动规
下一篇:华为机试 字符串分隔
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash