5 November
2024-08-27 22:38:13
拓扑排序
for (int i=1; i<=n; ++i) if (!ind[i]) q.push(i);
while (!q.empty()) {
int now=q.top(); q.pop(); printf("%d ", now);
for (int k=head[now]; k; k=nex[k])
if (--ind[to[k]]==0) q.push(to[k]);
}
神奇の背包 DP
现有 \(N\) 个物品和容积为 \(M\) 的背包. 物品的体积分别为 \(V_1, V_2, ..., V_N\). 求不选取物品 \(i\) 时, 装满背包的方案数量.
设 \(f(n, V)\) 为正向枚举的背包, \(g(n, V)\) 为反向枚举的背包, 则方案数为 \(\displaystyle \sum_{i=1}^{n}\sum_{j=0}^{m} f(i-1, j)\cdot g(i+1, m-j)\).
本次错误在于没有搞明白1维和2维背包的代码异同点:1维背包已经无需直接赋值,2维背包还是需要 \(f(i, j)=f(i-1, j)\) 的。
#include <cstdio>
int n, m, w[1003], f[1003][10003], g[1003][10003], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
f[0][0]=1;
for (int i=1; i<=n; ++i) {
for (int j=m; j>=w[i]; --j) f[i][j]=(f[i-1][j]+f[i-1][j-w[i]])%1014;
for (int j=w[i]-1; ~j; --j) f[i][j]=f[i-1][j]; // (*)
}
g[n+1][0]=1;
for (int i=n; i; --i) {
for (int j=m; j>=w[i]; --j) g[i][j]=(g[i+1][j]+g[i+1][j-w[i]])%1014;
for (int j=w[i]-1; ~j; --j) g[i][j]=g[i+1][j]; // (*)
}
for (int i=1; i<=n; ++i) {
ans=0;
for (int j=0; j<=m; ++j) ans=(ans+f[i-1][j]*g[i+1][m-j])%1014;
printf("%d ", ans);
}
return 0;
}
Sequence
给出数列 \(\{A_n\}\), 修改最少的元素, 使得数列 \(\{A_n\}\) 成为一个公差为 1 的等差数列.
预处理成数列 \(\{A_n-n\}\) 即可极大简化本题解法.
最新文章
- 在Android Studio中使用lambda表达式
- 2016年4月1日下午,《java入门123》翻开了第一页,从此走上不归路。新手初来乍到,献上见面礼
- iOS 进阶 第一天(0323)
- 基于cocos2d-x的游戏框架设计——李成
- TexturePacker的使用
- PHP的MVC框架 深入解析
- projecteuler----&;gt;problem=8----Largest product in a series
- My SQL数据库的安装与配置
- 一个爬取Bing每日壁纸的python脚本
- (转) 使用jdk的xjc命令由schema文件生成相应的实体类
- Gadgets for dollars and pounds CodeForces - 609D
- 原生JS实现圆周运动
- Selenium 4即将发布:每个QA都应该知道的
- windows 下安装 mongodb 时间太久,卡在那里不动
- 2-(基础入门篇)Air202下载开发入门(给Air202下载第一个程序)
- Android 自定义View二(深入了解自定义属性attrs.xml)
- aop的概述
- 202-React.Component组件、生命周期
- springMVC问题
- C/C++中RAND_MAX的用法