bzoj 1630: [Usaco2007 Demo]Ant Counting【dp】
2024-09-08 16:50:45
满脑子组合数学,根本没想到dp
设f[i][j]为前i只蚂蚁,选出j只的方案数,初始状态为f[0][0]=1
转移为
\[f[i][j]=\sum_{k=0}^{a[i]}f[i-1][j-k]
\]
\]
\[f[i][j]=\sum_{k=max(j-a[i],0)}^{j}f[i-1][k]
\]
\]
这样显然时空都不行,用滚动数组优化空间,前缀和优化时间即可
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005,mod=1000000;
int n,m,a[N],l,r,f[N*100],s[N],sum;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
int main()
{
n=read(),m=read(),l=read(),r=read();
for(int i=1;i<=m;i++)
{
int x=read();
a[x]++;
}
for(int i=0;i<=a[1];i++)
s[i]=1;
for(int i=1;i<=n;i++)
{
sum+=a[i];
for(int j=0;j<=sum;j++)
f[j]=(s[j]-((j-a[i]-1)<0?0:s[j-a[i]-1])+mod)%mod;
s[0]=f[0];
for(int j=1;j<=sum+a[i+1];j++)
s[j]=(s[j-1]+f[j])%mod;
}
printf("%d\n",(s[r]-s[l-1]+mod)%mod);
return 0;
}
最新文章
- C#检测驱动是否安装的问题
- Unable to find vcvarsall.bat的解决办法
- 理解JavaScript中的事件轮询
- Android 点击文字实现跳转
- 常用脚本语言Perl,Python,Ruby,Javascript一 Perl,Python,Ruby,Javascript
- 比较const ,readonly, stitac readonly
- 解决 Provider &#39;System.Data.SqlServerCe.3.5&#39; not installed. -摘自网络
- struts 2读书笔记-----struts2的开发流程
- Android端上传图片到后台,存储到数据库中 详细代码
- JS中表格的全选和删除要注意的问题
- 半透明边框与background-clip
- FEX(Fabric Extender)
- Python连接Access数据库遇到问题&#39;ADODB.Connection&#39;, &#39;未找到提供程序。该程序可能未正确安装。&#39;的处理办法
- 课程存储校对:程序设计思想、源程序代码、运行结果截图,以及开发过程中的项目计划日志、时间记录日志、缺陷记录日志(PSP0级记录)。
- HttpComponents组件探究 - HttpClient篇
- Egret打包App 短暂黑屏解决方案 (Egret4.1.0)
- BZOJ3239 Discrete Logging
- python实现lower_bound和upper_bound
- Poj 3318 Matrix Multiplication( 矩阵压缩)
- 系列文章(一):探究电信诈骗的关键问题与应对策略——By Me
热门文章
- private关键字
- linux shell &; man chmod
- 【数轴涂色+并查集路径压缩+加速】C. String Reconstruction
- Network-POJ3694(最小公共祖先LCA+Tarjin)
- springmvc @ResponseBody 乱码
- 通过ambari安装hadoop集群
- 改變iTunes備份路徑
- Effective C++ Item 41 了解隐式接口和编译期多态
- Office 佳能MP259打印EXCEL线条歪曲,字迹模糊怎么办
- C++之桟的应用---括号匹配