当前位置: 首页 > news >正文

【蓝桥杯专题】 DP(C++ | 洛谷 | acwing | 蓝桥)

菜狗现在才开始备战蓝桥杯QAQ

文章目录

  • 【蓝桥杯专题】 DP(C++ | 洛谷 | acwing | 蓝桥)
  • AcWing 1205. 买不到的数目
  • Acwing 1216. 饮料换购【模拟】
  • 01背包
  • 271. 杨老师的照相排列
  • 最长公共上升子序列
  • P
  • P
  • P
  • P
  • P
  • P
  • P
  • P
  • 总结

在这里插入图片描述

【蓝桥杯专题】 DP(C++ | 洛谷 | acwing | 蓝桥)

  • 看最后总结!!

AcWing 1205. 买不到的数目

链接 链接

  • 思路 暴力打表 找规律
#include <iostream>
using namespace std;int main () {int p, q;cin >> p >> q;cout << ((p - 1) * (q - 1) - 1) << endl;return 0;
} 

Acwing 1216. 饮料换购【模拟】

链接 链接

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int main()
{int n, ans ;cin >> n; ans = n;while((n / 3) >= 1) {// cout <<n <<endl;int t = n / 3;ans += t;n %= 3 ;n += t;}cout << ans << endl;    
}

01背包

链接 链接
在这里插入图片描述

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1010;int w[N], v[N];
int f[N][N];void solve () {int N, V;ll ans = 0;cin >> N >> V;rep(i, 1, N) {cin >> v[i] >> w[i];}
// 当前背包容量不够(j < v[i]),没得选,因此前 i 个物品最优解即为前 i−1个物品最优解:f[i][j] = f[i - 1][j]。
// 如果可以选 :f[i][j] = f[i - 1][j - v[i]] + w[i]。rep(i, 1, N) {    rep(j, 1, V) {if(j < v[i]) f[i][j] = f[i - 1][j];else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}}cout << f[N][V] << endl;
}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

271. 杨老师的照相排列

链接 链接
在这里插入图片描述


#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 31;ll f[N][N][N][N][N];void solve () {int n;while(cin >> n , n) {int s[5] = {0};rep(i, 0, n - 1) cin >> s[i];memset(f, 0 , sizeof f);f[0][0][0][0][0] = 1;   rep(a, 0, s[0]) {rep(b, 0, min(s[1], a)) {rep(c, 0, min(s[2], b)) {rep(d, 0, min(s[3], c)) {rep(e, 0, min(s[4], d)) {// f[a][b][c][d][e]代表从后往前每排人数分别为a, b, c, d, e的所有方案的集合, 其中a >= b >= c >= d >= e; 逆序的
// f[a][b][c][d][e]的值是该集合中元素的数量;ll &x = f[a][b][c][d][e];if (a && a - 1 >= b) x += f[a - 1][b][c][d][e];if (b && b - 1 >= c) x += f[a][b - 1][c][d][e];if (c && c - 1 >= d) x += f[a][b][c - 1][d][e];if (d && d - 1 >= e) x += f[a][b][c][d - 1][e];if (e) x += f[a][b][c][d][e - 1];// 当a > 0 && a - 1 >= b时,最后一个同学可能被安排在第1排,方案数是f[a - 1][b][c][d][e];
// 当b > 0 && b - 1 >= c时,最后一个同学可能被安排在第2排,方案数是f[a][b - 1][c][d][e];
// 当c > 0 && c - 1 >= d时,最后一个同学可能被安排在第3排,方案数是f[a][b][c - 1][d][e];
// 当d > 0 && d - 1 >= e时,最后一个同学可能被安排在第4排,方案数是f[a][b][c][d - 1][e];
// 当e > 0时,最后一个同学可能被安排在第5排,方案数是f[a][b][c][d][e - 1];} }}}}cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;}}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

最长公共上升子序列

链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 3111;int a[N], b[N];
int f[N][N];void solve () {int n ;cin >> n;rep(i, 1, n) cin>> a[i];rep(i, 1, n) cin>> b[i];//版本1// rep(i, 1, n) {//     rep(j, 1 , n) {//         f[i][j] = f[i - 1][j];//         if(a[i] == b[j]) {//             // int maxv = 1;  // O(n^ 3)//             // for(int k =1; k < j; k ++) {//             //     if(b[j] > b[k]) {//             //         maxv = max(maxv, f[i - 1][k] + 1);//             //     }//             //     f[i][j] = max(maxv, f[i][j]);//             // }//         }//     }// }//版本2: rep(i, 1, n) {int maxv = 1;rep(j, 1, n) {f[i][j] = f[i - 1][j];if(a[i] == b[j] ) f[i][j] = max(maxv, f[i][j]);if(a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);}}int res = 0;rep(i, 1, n) {res = max(res, f[n][i]);}cout << res << endl;}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}
# P
[链接 链接]( )

P

链接 链接

P

链接 链接

P

链接 链接

P

链接 链接

P

链接 链接

P

链接 链接

P

链接 链接

P

链接 链接

总结

  • 数论别浪费太多时间, 做法暴力打表找规律 , 能做出来就做
  • exit(0) 调试bug 针对没有输出的时候好用
  • DP 多刷 (大部分题型)

在这里插入图片描述

相关文章:

【蓝桥杯专题】 DP(C++ | 洛谷 | acwing | 蓝桥)

菜狗现在才开始备战蓝桥杯QAQ 文章目录【蓝桥杯专题】 DP&#xff08;C | 洛谷 | acwing | 蓝桥&#xff09;AcWing 1205. 买不到的数目Acwing 1216. 饮料换购【模拟】01背包271. 杨老师的照相排列最长公共上升子序列PPPPPPPP总结【蓝桥杯专题】 DP&#xff08;C | 洛谷 | acwi…...

咪咕MGV3201_ZG_GK国科6323_UWE5621DS_免拆卡刷固件包

咪咕MGV3201_ZG_GK国科6323_UWE5621DS_免拆卡刷固件包 特点&#xff1a; 1、适用于对应型号的电视盒子刷机&#xff1b; 2、开放原厂固件屏蔽的市场安装和u盘安装apk&#xff1b; 3、修改dns&#xff0c;三网通用&#xff1b; 4、大量精简内置的没用的软件&#xff0c;运行…...

重构数据-Change Value to Reference将实值对象改为引用对象三

重构数据-Change Value to Reference将实值对象改为引用对象三 1.将实值对象改为引用对象 1.1.实值对象和引用对象区别 下面通过客户Customer和订单Order两个对象介绍下它们的区别 值对象&#xff1a;当一个客户Customer下了多个订单Order后&#xff0c;每个订单类都将创建一…...

计算机网络——通信专业面试问题学习笔记

文章目录1、计算机网络这门课学了什么&#xff1f;目录里有多少章&#xff1f;2、Internet的概念与发展史3、什么是交换&#xff1f;三种交换方式4、OSI的七层协议, TCP/IP的四层协议, 五层协议5、WAN 、LAN 、MAN、PAN这些能分的清楚吗&#xff1f;全称分别都是什么&#xff1…...

代码随想录算法训练营第三十天 | 332.重新安排行程 51. N皇后 37. 解数独 总结

打卡第30天&#xff0c;回溯算法第二刷。 今日任务 332.重新安排行程51.N皇后37.解数独总结 332.重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从…...

Windows权限提升—MySQL数据库提权

Windows权限提升—MySQL数据库提权1. 前言2. 数据库提权介绍2.1. 常见数据库端口2.2. MySQL数据库提权条件2.3. MySQL数据库提权类型3. MySQL中UDF提权3.1. UDF提权介绍3.2. UDF提权思路3.3. UDF提权步骤3.3.1. 获取外连数据库3.3.1.1. 外连数据库3.3.1.2. 连接数据库3.3.1.3. …...

使用旧电脑玩Linux

今天给大家讲讲使用旧电脑玩Linux&#xff0c;大家应该都知道旧电脑的硬件一般比较落后&#xff0c;特别是一些非常老的电脑&#xff0c;目前还在使用的是机械硬盘&#xff0c;如是要跑windows可想而知&#xff0c;但是Linux系统对硬件性能的要求可比windows低的多了&#xff0…...

Linux安装EMQX(简洁版)

安装目录 mkdir /opt/emqx && cd /opt/emqx 安装包下载 yum -y install wget && wget https://www.emqx.com/zh/downloads/broker/5.0.20/emqx-5.0.20-el7-amd64.tar.gz 注意&#xff1a;https://www.emqx.com/zh/downloads/broker获取下载链接并替换(后缀&…...

基于STM32 + FPGA 的软体机器人的 CAN总线运动控制器的设计

针对在软体机器人控制时&#xff0c;多电机协同控制过程中难度大、通用性差、协同性差等缺点&#xff0c;设计了基于 A&#xff32;M和 FPGA的软体机器人的控制器局域网络 ( controller area network&#xff0c;CAN) 总线运动控制器&#xff0c;采用 A&#xff32;MCortex-M4 …...

ROC曲线和AUC值

ROC曲线&#xff08;Receiver Operating Characteristic&#xff0c;受试者工作特征&#xff09;评价分类模型的可视化工具&#xff0c;是一条横纵坐标都限制在0-1范围内的曲线横坐标是假正率FPR&#xff0c;错误地判断为正例的概率纵坐标是真正率TPR&#xff0c;正确地判断为正…...

【vue.js】在网页中实现一个金属抛光质感的按钮

文章目录前言效果电脑效果手机效果说明完整代码index.html前言 诶&#xff1f;这有一个按钮(&#xff5e;&#xffe3;▽&#xffe3;)&#xff5e;&#xff0c;这是一个在html中实现的具有金属质感并且能镜面反射的按钮~ 效果 电脑效果 手机效果 说明 主要思路是使用 navig…...

android实现评论区功能

效果 activity_detail.xml <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"xmlns:tools"http…...

Java每日一练(20230319)

目录 1. 最大矩形 &#x1f31f;&#x1f31f;&#x1f31f; 2. 回文对 &#x1f31f;&#x1f31f;&#x1f31f; 3. 给表达式添加运算符 &#x1f31f;&#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练…...

Redis缓存双写一致性

目录双写一致性Redis与Mysql双写一致性canal配置流程代码案例双写一致性理解缓存操作细分缓存一致性多种更新策略挂牌报错,凌晨升级先更新数据库,在更新缓存先删除缓存,在更新数据库先更新数据库,在删除缓存延迟双删策略总结双写一致性 Redis与Mysql双写一致性 canal 主要是…...

【2023-Pytorch-检测教程】手把手教你使用YOLOV5做交通标志检测

项目下载地址&#xff1a;YOLOV5交通标志识别检测数据集代码模型教学视频-深度学习文档类资源-CSDN文库 交通标志的目标检测算法在计算机视觉领域一直属于热点研究问题&#xff0c;改进的优化算法不断地被提出。国内外许多学者针对现有的目标检测方法中网络结构、目标定位、损…...

Java中的二叉树

文章目录前言一、树形结构&#xff08;了解&#xff09;1.1 概念1.2 概念&#xff08;重要&#xff09;1.3 树的表示形式&#xff08;了解&#xff09;1.4 树的应用二、二叉树&#xff08;重点&#xff09;2.1 概念2.2 两种特殊的二叉树2.3 二叉树的性质2.5 二叉树的存储2.5 二…...

基于 gma 绘制古代洛阳 5 大都城遗址空间分布地图

了解 gma gma 是什么&#xff1f; gma 是一个基于 Python 的地理、气象数据快速处理和数据分析函数包&#xff08;Geographic and Meteorological Analysis&#xff0c;gma&#xff09;。gma 网站&#xff1a;地理与气象分析库。 gma 的主要功能有哪些&#xff1f; 气候气象&a…...

分析 Spring 的依赖注入模式

一、依赖注入二、Field Injection优点缺点三、Constructor Injection优点1. 容易发现 code smell优点2. 容易厘清依赖关系优点3. 容易写单元测试优点4. Immutable Object缺点&#xff1a;循环依赖四、总结一、依赖注入 依赖注入 &#xff08;Dependency Injection&#xff0c;…...

IntelliJ IDEA创建Servlet

目录 ——————————————————————————————— 一、创建Java项目 1、创建java项目 2、选择java 3、next 4、给项目命名 5、新创建完java项目的目录结构 二、变java为servlet项目 1、变servlet项目 2、选择Web Application 3、更新完成后的目录…...

Spring Boot如何让自己的bean优先加载

背景介绍 在一些需求中&#xff0c;可能存在某些场景&#xff0c;比如先加载自己的bean&#xff0c;然后自己的bean做一些DB操作&#xff0c;初始化配置问题&#xff0c;然后后面的bean基于这个配置文件&#xff0c;继续做其他的业务逻辑。因此有了本文的这个题目。 实现方法…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...