【BZOJ1630/2023】[Usaco2007 Demo]Ant Counting DP
2024-09-12 15:15:35
【BZOJ1630/2023】[Usaco2007 Demo]Ant Counting
题意:T中蚂蚁,一共A只,同种蚂蚁认为是相同的,有一群蚂蚁要出行,个数不少于S,不大于B,求总方案数
题解:DP,先列出朴素的方程,用f[i][j]表示前i种,出行j只的方案数,v[i]代表第i中蚂蚁的个数
f[i][j]=∑f[i-1][j-k] (0≤k≤min(j,v[i]))
也可以表示为
f[i][j]=∑f[i-1][k] (j-min(j,v[i])≤k≤j)
发现时间复杂度为均摊O(A^2),那么我们可以用前缀和优化,空间复杂度为O(T*A),我们可以采用滚动数组
关于数据范围什么的,反正O(T*A)过了,题目描述233
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define mod 1000000
using namespace std;
int f[2][100010],s[2][100010];
int n,m,l,r;
int v[100010];
int main()
{
int i,j,k,a;
scanf("%d%d%d%d",&n,&m,&l,&r);
for(i=1;i<=m;i++)
{
scanf("%d",&a);
v[a]++;
}
for(i=0;i<=m;i++) s[0][i]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(j<=v[i]) f[i&1][j]=s[(i&1)^1][j];
else f[i&1][j]=(s[(i&1)^1][j]-s[(i&1)^1][j-v[i]-1]+mod)%mod;
if(!j) s[i&1][j]=f[i&1][j];
else s[i&1][j]=(s[i&1][j-1]+f[i&1][j])%mod;
}
}
printf("%d",(s[n&1][r]-s[n&1][l-1]+mod)%mod);
return 0;
}
最新文章
- VS2015开发Android,自带模拟器无法调试、加载程序,算是坑吗
- 标准BST二叉搜索树写法
- Objective C中的ARC的修饰符的使用---- 学习笔记九
- 把cmd信息中的正常和异常输出分别输出到不同txt文件中
- JavaSE之概述与基本语法
- jquery添加光棒效果的各种方式以及简单动画复杂动画
- dump_stack调用过程【原创】
- Linux启动时卡住
- ios真机调试详细步骤
- 项目由Windows2003 迁移到Windows 2008 过程,报 JS错误
- 从spark架构中透视job
- 【HDOJ】1813 Escape from Tetris
- jQuery源代码 解析一 工具方法
- PS 过滤器——运动模糊
- IIS 7.5配置PHP站点
- toastr 通知提示插件
- POJ 1321 棋盘问题(DFS板子题,简单搜索练习)
- 实例详析ImageView的adjustViewBonds和scaleType
- 数据库---mysql的介绍和安装
- GDAL 地图切片层级计算公式
热门文章
- android EditText设置光标、边框和图标,以及限制输入
- mongodb自动关闭:页面太小,无法完成操作
- [转]MySQL远程连接ERROR 2003 (HY000):Can&#39;t connect to MySQL server on&#39;XXXXX&#39;(111) 的问题
- Supervision 行为模式
- R语言boxplot绘图函数
- Fastqc 能够识别的碱基编码格式
- 教你如何架设linux邮件服务器postfix
- CleanMyMac 3.7.5最强中文版_激活码_破解版_下载_注册码
- Xcode 5.0 编译低版本app
- 网页中Span和Div的区别