POJ3046--Ant Counting(动态规划)
Being a bit mathematical, Bessie started wondering. Bessie noted that the hive has T (1 <= T <= 1,000) families of ants which she labeled 1..T (A ants altogether). Each family had some number Ni (1 <= Ni <= 100) of ants.
How many groups of sizes S, S+1, ..., B (1 <= S <= B <= A) can be formed?
While observing one group, the set of three ant families was seen as {1, 1, 2, 2, 3}, though rarely in that order. The possible sets of marching ants were:
3 sets with 1 ant: {1} {2} {3}
5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}
5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}
1 set with 5 ants: {1,1,2,2,3}
Your job is to count the number of possible sets of ants given the data above.
Input
* Lines 2..A+1: Each line contains a single integer that is an ant type present in the hive
Output
Sample Input
3 5 2 3
1
2
2
1
3
Sample Output
10
Hint
Three types of ants (1..3); 5 ants altogether. How many sets of size 2 or size 3 can be made?
OUTPUT DETAILS:
5 sets of ants with two members; 5 more sets of ants with three members
#include<iostream>
#include<algorithm>
#include<string.h>
int dp[][];
int num[];
#define MOD 1000000
using namespace std;
int main(){
int t,a,s,b;
cin>>t>>a>>s>>b;
for(int i=;i<=a;i++){
int x;
cin>>x;
num[x]++;
}
dp[][]=;
int total=;
for(int i=;i<=t;i++){
total+=num[i];
memset(dp[i%],,sizeof(dp[i%]));
for(int j=;j<=total;j++){
for(int k=;k<=num[i];k++){
dp[i%][j]=(dp[i%][j]+dp[(i-)%][j-k])% MOD;
}
}
}
int ans=;
for(int i=s;i<=b;i++){
ans=(ans+dp[t%][i])% MOD;
}
cout<<ans<<endl;
return ;
}
最新文章
- Invoke--转载
- 入侵本地Mac OS X的详细过程 转自https://yq.aliyun.com/articles/22459?spm=5176.100239.blogcont24250.10.CfBYE9
- SparkContext源码阅读
- 【转】提高C#编程水平的50个要点
- nodejs学习笔记<;五>;npm使用
- 转:java日志组件介绍(common-logging,log4j,slf4j,logback )
- 读书笔记:Ross:概率模型导论:方差和协方差
- 《MFC游戏开发》笔记四 键盘响应和鼠标响应:让人物动起来
- oracle Execute Immediate 用法
- 时效性福利:MindManager2017 破解攻略
- jQuery制作右侧边垂直二级导航菜单
- 【最大流ISAP】洛谷P3376模板题
- Java第五周总结
- 转载 linux基本操作
- mysql之整型数据int
- Linux常用内核参数
- html5实现获取地理位置信息并定位
- 常见笔记本进入bios方法
- CentOS7 如何修改 内核版本
- 教你摆脱低级程序猿 项目中cocopads的安装使用
热门文章
- Django 模板语言 路由 视图
- 8M - 三角形
- Cookie 和 Session 的区别和联系?session的生命周期?多个服务器部署session的管理?
- SD-WAN介绍
- 06. pt-duplicate-key-checker
- ubuntu下firefox打开mht文件
- laravel错误1071 Specified key was too long; max key length is 1000 bytes
- python连接Linux服务器
- hbase 单机版安装
- [IBM][CLI Driver][DB2/NT] SQL1101N 不能以指定的授权标识和密码访问节点 ";"; 上的远程数据库 ";LBZM";。 SQLSTATE=08004