当前位置:网站首页>LeetCode 6109. 知道秘密的人数
LeetCode 6109. 知道秘密的人数
2022-07-05 18:12:00 【HumbleFool】
LeetCode 6109. 知道秘密的人数
线性DP + 前缀和优化
/* f[i][j]表示前i天,记得秘密j天的数量 j == 1: 一共有 delay <= j < forget数量 f[i][j] = f[i - 1][delay] + f[i - 1][delay + 1] ... f[i - 1][forget - 1]; 这里求了连续和,暴力n^3,会超时,前缀和优化 f[i][j] = f[i - 1][forget - 1] - f[i - 1][delay - 1]; j > 1: f[i][j] = f[i - 1][j - 1]; f[i][j] = f[i - 1][j - 1] - f[i - 1][j - 2] */
const int N = 1010, MOD = 1e9 + 7;
class Solution {
public:
int f[N][N];
int peopleAwareOfSecret(int n, int delay, int forget) {
for(int i = 1; i <= forget; i ++) f[1][i] = 1;
for(int i = 2; i <= n; i ++)
{
for(int j = 1; j <= forget; j ++)
{
if(j > 1) f[i][j] = (f[i - 1][j - 1] - f[i - 1][j - 2]) % MOD;
else if(j == 1) f[i][j] = (f[i - 1][forget - 1] - f[i - 1][delay - 1]) % MOD;
f[i][j] = (f[i][j] + f[i][j - 1]) % MOD;
}
}
return (f[n][forget] + MOD) % MOD;
}
};
边栏推荐
- Gimp 2.10 tutorial "suggestions collection"
- 集群部署如何解决海量视频接入与大并发需求?
- buuctf-pwn write-ups (9)
- RSE2020/云检测:基于弱监督深度学习的高分辨率遥感图像精确云检测
- 访问数据库使用redis作为mysql的缓存(redis和mysql结合)
- 小林coding的内存管理章节
- 【在优麒麟上使用Electron开发桌面应】
- 星环科技数据安全管理平台 Defensor重磅发布
- 彻底理解为什么网络 I/O 会被阻塞?
- How to solve the error "press any to exit" when deploying multiple easycvr on one server?
猜你喜欢
随机推荐
ISPRS2022/云检测:Cloud detection with boundary nets基于边界网的云检测
破解湖+仓混合架构顽疾,星环科技推出自主可控云原生湖仓一体平台
金太阳开户安全吗?万一免5开户能办理吗?
nacos -分布式事务-Seata** linux安装jdk ,mysql5.7启动nacos配置ideal 调用接口配合 (保姆级细节教程)
LeetCode 6111. 螺旋矩阵 IV
Xiaobai getting started with NAS - quick building private cloud tutorial series (I) [easy to understand]
图像分类,看我就够啦!
写作写作写作写作
南京大学:新时代数字化人才培养方案探讨
Isprs2022 / Cloud Detection: Cloud Detection with Boundary nets Boundary Networks Based Cloud Detection
nano的CAN通信
[BeanShell] there are many ways to write data locally
Binder开辟线程数过多导致主线程ANR异常
第十一届中国云计算标准和应用大会 | 华云数据成为全国信标委云计算标准工作组云迁移专题组副组长单位副组长单位
兄弟组件进行传值(显示有先后顺序)
JVM third talk -- JVM performance tuning practice and high-frequency interview question record
What is the reason why the video cannot be played normally after the easycvr access device turns on the audio?
开户复杂吗?网上开户安全么?
如何获取飞机穿过雷达两端的坐标
吳恩達團隊2022機器學習課程,來啦