【hdu4045】Machine scheduling(dp+第二类斯特林数)
2024-10-18 22:52:29
题意:
从\(n\)个人中选\(r\)个出来,但每两个人的标号不能少于\(k\)。
再将\(r\)个人分为不超过\(m\)个集合。
问有多少种方案。
思路:
直接\(dp\)预处理出从\(n\)个人选\(r\)个的方案,第二类斯特拉数处理分组的情况即可。
/*
* Author: heyuhhh
* Created Time: 2019/12/10 19:14:48
* dp预处理+第二类斯特林数
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1005, MOD = 1e9 + 7;
void add(int &x, int y) {
x += y;
if(x >= MOD) x -= MOD;
}
int n, m, r, k;
int dp[N][N];
int s[N][N];
void init() {
s[0][0] = 1;
for(int i = 1; i < N; i++)
for(int j = 1; j <= i; j++)
s[i][j] = (1ll * j * s[i - 1][j] % MOD + s[i - 1][j - 1]) % MOD;
}
void run(){
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
dp[i][0] = 1;
for(int j = 1; j <= r; j++) {
add(dp[i][j], dp[i - 1][j]);
add(dp[i][j], dp[max(i - k, 0)][j - 1]);
}
}
int tot = dp[n][r];
int sum = 0;
for(int i = 1; i <= m; i++) add(sum, s[r][i]);
int ans = 1ll * tot * sum % MOD;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
init();
while(cin >> n >> r >> k >> m) run();
return 0;
}
最新文章
- KNN近邻算法
- XML(DOM解析)
- sql order by 排序多个字段
- C# Excel写入
- 高通APQ8074 spi 接口配置
- Shell script for logging cpu and memory usage of a Linux process
- TransactionScope使用
- 《C语言程序设计现代方法》第3章 格式化输入/输出
- ICON图标文件解析
- Google浏览器调试js
- Intellij Idea web项目的部署配置[转]
- css3部分属性兼容性别扭写法(因为很多我就叫他别扭了,希望全面早早支持css3吧)
- zf-关于SYS_User表type的分类
- ActiveMQ安装及启动
- PAT乙级-1036.跟奥巴马一起编程(15)
- 【Java】运用泽勒一致性计算某天是星期几
- Python内置函数(47)——open
- javascript基础常识了解一下
- python命令随记
- JAVA IO流 InputStream流 Read方法
热门文章
- Spring中常见的设计模式——委派模式
- .net core 2.1 Nlog.Web.AspNetCore Nlog日志
- JavaWeb入门——Tomcat的目录结构
- LeetCode刷题191203 --回溯算法
- Redis集群模式下的redis-py-cluster方式读写测试
- centos7在线yum安装mysql时官方镜像下载过慢的解决方案
- Linux后台运行和关闭jar项目
- select同时获取value和label的值
- 《Web Development with Go》Mangodb查询collection内所有记录
- 《移动WEB前端高级开发实践@www.java1234.com》——3