组合数学+费用背包+刷表,G2 - Playlist for Polycarp (hard version)
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
| G2 - Playlist for Polycarp (hard version) |
二、解题报告
1、思路分析
一眼dp,但是这个dp思路和代码都不太好想
首先是涉及到组合数学的分配问题
方案数怎么求?
既涉及到了相邻的顺序,又涉及到了容量/费用
我们可以单独考虑然后相乘:
f(i, j, k, x) 为 选取 i 个类型1,j个 类型2,k 个类型3,并且以类型x结尾,且无相同相邻项的方案数
这个dp可太简单了,O(1)转移,O(N^3 * 3)的方案数,很好搞定
再考虑 g(i, j, k, t) 即 选 i 个类型1,j个 类型2,k 个类型3,总费用为t(费用指的是时间和)的方案数
这是个费用背包问题,我们直接求是O(N ^ 4 T),太大了
考虑转换一下,g(j, k, p) 为 j个 类型2,k 个类型3 总费用为t方案数,h(i, T - p)为i个类型1,总费用为t的方案数,乘法原理二者相乘可得
然后 (f(i, j, k, 0) + f(i, j, k, 1) f(i, j, k, 2)) * g(j, k, p) * h(i, T - p) * fac(i) * fac(j) * fac(k) 就是一组方案数
什么意思?
f 确定了每个类型放的位置,然后每个类型的每个物品是不同的,这就是一个多重集排列问题
然后 h 和 t 又确定了选取哪些类型1、2、3,再根据乘法原理乘一块就是答案
2、复杂度
时间复杂度: O(N^3 T)空间复杂度:O(N^ T)
3、代码详解
#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
using PII = std::pair<int, int>;
constexpr int N = 55, M = 2505, P = 1'000'000'007;void add(int& x, int y) { x += y, (x >= P) && (x -= P); }
int fac[N], f[N][N / 2][N / 3][3], g[N / 2][N / 3][M], h[N][M];void solve() {int n, T;std::cin >> n >> T;fac[0] = 1;for (int i = 1; i <= n; ++ i) fac[i] = 1LL * i * fac[i - 1] % P;std::vector<int> a, b, c;std::vector<std::array<int, 3>> cnt(n);for (int i = 0, t, g; i < n; ++ i) {std::cin >> t >> g;if (g == 1) a.push_back(t);if (g == 2) b.push_back(t);if (g == 3) c.push_back(t);}if (a.size() < b.size())std::swap(a, b);if (a.size() < c.size()) std::swap(a, c);if (b.size() < c.size())std::swap(b, c);int A = a.size(), B = b.size(), C = c.size();// 求费用背包g[0][0][0] = 1;for (int i = 0; i < B; ++ i) for (int j = i; ~j; -- j) for (int p = T - b[i]; p >= 0; -- p)add(g[j + 1][0][p + b[i]], g[j][0][p]);for (int i = 0; i < C; ++ i)for (int j = B; j >= 0; -- j)for (int k = i; k >= 0; -- k)for (int p = T - c[i]; p >= 0; -- p) add(g[j][k + 1][p + c[i]], g[j][k][p]);h[0][0] = 1;for (int i = 0; i < A; ++ i) for (int j = i; ~j; -- j) for (int p = T - a[i]; p >= 0; -- p) add(h[j + 1][p + a[i]], h[j][p]);// 刷表f[1][0][0][0] = f[0][1][0][1] = f[0][0][1][2] = 1;for (int i = 0; i <= A; ++ i)for (int j = 0; j <= B; ++ j)for (int k = 0; k <= C; ++ k) {for (int x = 0, v; x < 3; ++ x) {if (v = f[i][j][k][x]) {if (x) add(f[i + 1][j][k][0], v);if (x ^ 1) add(f[i][j + 1][k][1], v);if (x ^ 2) add(f[i][j][k + 1][2], v);}}add(f[i][j][k][0], f[i][j][k][1]);add(f[i][j][k][0], f[i][j][k][2]);f[i][j][k][0] = 1LL * f[i][j][k][0] * fac[i] % P * fac[j] % P * fac[k] % P;}int res = 0;for (int j = 0; j <= B; ++ j)for (int k = 0; k <= C; ++ k)for (int p = 0; p <= T; ++ p)if (g[j][k][p])for (int i = 0; i <= A; ++ i)if (h[i][T - p])add(res, 1LL * f[i][j][k][0] * g[j][k][p] % P * h[i][T - p] % P);std::cout << res;
}int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifstd::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}
相关文章:
组合数学+费用背包+刷表,G2 - Playlist for Polycarp (hard version)
目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 G2 - Playlist for Polycarp (hard version) 二、解题报告 1、思路分析 一…...
阿尔泰科技利用485模块搭建自动灌溉系统实现远程控制
自动灌溉系统又叫土壤墒情监控系统,土壤墒情监控系统主要实现固定站无人值守情况下的土壤墒情数据的自动采集和无线传输,数据在监控中心自动接收入库;可以实现24小时连续在线监控并将监控数据通过有线、无线等传输方式实时传输到监控中心生成…...
Python正则表达式中的分组
表达式中的分组 它是可以通过" () “来进行分组,更专业的表达就是捕获组,每个完整的” () “可以分为一组,同时,” () “中还可以嵌套” () ",即组之间还可以存在更小的组 概念 1、当我们在一个正则表达式…...
openstack设置IP直接登录,不需要加dashboard后缀
openstack 实验环境,openstack-t版,centos2009 修改配置文件 [rootcontroller ~]# vim /WEBROOT /etc/openstack-dashboard/local_settings #将dashboard去掉 WEBROOT /dashboard/ #改为 WEBROOT /[rootcontroller ~]# vim /etc/httpd/conf.d/openst…...
PHP宠物店萌宠小程序系统源码
🐾萌宠生活新方式🐾 🏡【一键直达萌宠世界】 你是否也梦想着拥有一家随时能“云撸猫”、“云吸狗”的神奇小店?现在,“宠物店萌宠小程序”就是你的秘密花园!🌟只需轻轻一点,就能瞬…...
nginx负载均衡实例
实现效果 浏览器输入地址http://nginx服务器ip(:80)/edu/a.html,实现负债均衡效果,平均分配到 服务器ip:8080和 服务器ip:8081进程中。 准备工作 准备两个tomcat,一个监听在8080端口,一个监听在8081端口。也可以准备多个tomcat。…...
正则表达式在Python中的高级应用:从HTML中提取数据
正则表达式在Python中的高级应用:从HTML中提取数据 作为一名资深的Python程序员,我深知正则表达式在文本处理中的重要性。尤其是在处理HTML文档时,正则表达式可以成为我们提取数据的强大工具。在本文中,我将通过一个实际的例子&a…...
docker compose 部署交互模式的容器-以Ubuntu为例
docker compose 部署交互模式的容器-以Ubuntu为例 问题介绍解决方式 同步发布在个人笔记docker compose 部署交互模式的容器-以Ubuntu为例 问题介绍 想通过 docker compose 方式部署一个交互模式的 Ubuntu 容器,但是以平常的方式执行部署后,发现容器被创…...
display: flex 和 justify-content: center 强大居中
你还在为居中而烦恼吗,水平居中多个元素、创建响应式布局、垂直和水平同时居中内容。它,display: flex 和 justify-content: center 都可以完成! display: flex:将元素定义为flex容器 justify-content:定义项目在主轴…...
记录贴-idea导入别人的项目
链接: IDEA导入Web项目的三种方式 链接: idea怎么导入别人的maven项目 链接: IDEA 如何导入别人的javaweb项目进行部署...
算法第九天:leetcode59.螺旋矩阵II
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1: 输入:n 3 输出:[[1,2,3],[8,9,4],[7,6,5]]示例 2: 输入:n 1 输出&am…...
androidkiller重编译apk失败的问题
androidkiller重编译apk失败 参考: https://blog.csdn.net/qq_38393271/article/details/127057187 https://blog.csdn.net/hkz0704/article/details/132855098 已解决:“apktool” W: invalid resource directory name:XXX\res navigation 关键是编译…...
matlab中plot的一些用法
文章目录 一、基本用法二、绘制多个数据集三、设置线型、颜色四、添加标题和标签五、添加图例六、设置轴范围七、绘制网格八、 在同一图中绘制多个子图九、绘制带误差条的图十、绘制半对数图和对数图十一、绘制填充区域图十二、综合案例 一、基本用法 x 0:0.1:10; y sin(x);…...
Elasticsearch:Retrievers 介绍 - Python Jupyter notebook
在今天的文章里,我是继上一篇文章 “Elasticsearch:介绍 retrievers - 搜索一切事物” 来使用一个可以在本地设置的 Elasticsearch 集群来展示 Retrievers 的使用。在本篇文章中,你将学到如下的内容: 从 Kaggle 下载 IMDB 数据集…...
5 webSocket
webSockets 简介 什么是 websocket webSockets 是一种先进的技术;它可以在用户的浏览器和服务器之间打开交互式通信会话;使用此 API,您可以向服务器发送消息并接收事件驱动的响应,而无需通过轮询服务器的方式以获得响应 websocket 是一种网络通信协议,是HTML5开始提供的一种在单…...
PD芯片诱骗取电电压给后端小家电用电:LDR6328
在智能家居浪潮的推动下,小家电作为日常生活中不可或缺的一部分,其供电方式的创新与优化正逐步成为行业关注的焦点。随着快充技术的普及,特别是Power Delivery(PD)协议的广泛应用,一种新型供电模式——利用…...
深入解析Linux文件权限管理:掌握`chmod`和`chown`命令
深入解析Linux文件权限管理:掌握chmod和chown命令 深入解析Linux文件权限管理:掌握chmod和chown命令 大纲:摘要:内容: 1. 引言2. 理解文件权限3. 使用chmod命令4. 使用chown命令5. 综合应用6. 常见问题与解决方案7. 结…...
3.Implementing Controllers
Implementing Controllers 控制器提供了对应用程序行为的访问,这些行为通常通过一个服务接口来定义。控制器解释用户输入,并将其转换为由视图展示给用户的模型。Spring 以非常抽象的方式实现了控制器,使得你能够创建各种各样的控制器。 Spr…...
如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow
Git Flow、GitHub Flow 和 GitLab Flow 是几种常见的 Git 分支管理策略,它们帮助开发团队更高效地管理代码库和协同开发。 Git Flow Git Flow 是一种功能强大的分支管理模型,由 Vincent Driessen 提出,适用于发布周期较长、需要严格管理发布…...
Java垃圾收集器选择与优化策略
1.垃圾收集算法有哪些,可以聊一下吗? 如何确定一个对象是垃圾? 要想进行垃圾回收,得先知道什么样的对象是垃圾。 1.1 引用计数法 对于某个对象而言,只要应用程序中持有该对象的引用,就说明该对象不是垃圾。如果一个对象没有任何指针对其引用,它就是垃圾。 弊端:如果…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...


