马上蓝桥杯了,干货总结动态规划专题,祝你考场爆杀(拔高篇)最佳课题选择 书本整理 打鼹鼠 吃吃吃 非零字段划分

本文主要是介绍马上蓝桥杯了,干货总结动态规划专题,祝你考场爆杀(拔高篇)最佳课题选择 书本整理 打鼹鼠 吃吃吃 非零字段划分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

最佳课题选择

思路: 

书本整理

思路: 

打鼹鼠 

思路: 

吃吃吃

思路:

非零字段划分


        

        

最佳课题选择

思路: 

根本还是论文的分配,每个课题分配多少个论文是不确定的,这个也是很影响转移的。

也就是说当前已经遍历到第i个课题,那么从i-1课题转移过来的论文数应该依次遍历取最优。

那么设置f[i][j]已经遍历到第i个课题,且已经分配了j个论文对应的总花费时间。

f[i][j]=min(f[i-1][j-k]+f(k))   k<j          f(k)表示i-1个课题在k个论文下对应的花费

要额外注意初始化问题:
对于第一个课题对应所有论文情况都要初始化才行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205;
ll n,m,inf=1e18,a[N],b[N],f[N][N];
int main(){cin>>n>>m;for(int i=1;i<=m;i++)cin>>a[i]>>b[i];f[1][0]=0;for(int i=1;i<=n;i++)f[1][i]=a[1]*(ll)pow(i,b[1]);//注意隐式转换for(int i=2;i<=m;i++)for(int j=0;j<=n;j++){long long tmp=inf;for(int k=0;k<=j;k++){tmp=min(tmp,f[i-1][j-k]+a[i]*(ll)pow(k,b[i]));}f[i][j]=tmp;//获取最小的结果}cout<<f[m][n];return 0;
}

        

        

书本整理

思路: 

一定用好排序后的结果,我们注意到状态的转移和每次拿走的书关系不大,而是和其两旁的书关系很大,所以免不了我们需要关注每次拿走书的两旁的书,额?动态规划这么去想还写个屁呀!动态规划一定是从小状态到大状态的,不是从大状态到小状态的!!!

既然拿书不行我们就放书,注意到拿走书和那本书不放是等价的,而每本书都有放和不放

如果设置f[i][j]表示遍历到i本书(i书留下),当前总共留下了j本书对应的最小不整齐度。

你都知道了之前留下的书是哪一本了,后面的转移也就有了依据:

f[i][l]=min(f[j][l-1]+abs(a[i].y-a[j].y))     j<i    l<min(i,m)

看不懂我解释一下:当前第i本留下,且一共留下l本书的情况可以从第i-1本留下且一共留下l-1本转移,也可以从第i-2,i-3……本留下且一共留下l-1本转移,那么我们只需要用到a[i]和a[j]即可。

#include <bits/stdc++.h>
using namespace std;
int f[300][300],n,k,ans=1e8;
struct node {int x,y;}a[300];
bool cmp(node c,node d){if(c.x!=d.x)return c.x<d.x;else return c.y<d.y;
}
int main(){cin>>n>>k;int m=n-k;for(int i=1;i<=n;i++){cin>>a[i].x >>a[i].y;}sort(a+1,a+1+n,cmp);memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++)f[i][1]=0;for(int i=2;i<=n;i++)//i是尝试放第i本书for(int j=1;j<i;j++){for(int l=2;l<=min(i,m);l++){//l是留下的本书f[i][l]=min(f[i][l],f[j][l-1]+abs(a[i].y-a[j].y));}}for(int i=m;i<=n;i++)ans=min(ans,f[i][m]);cout<<ans;
}

        

        

打鼹鼠 

思路: 

m个时间,每个时间都有一个鼹鼠出现,如果我们尝试去找起点跑图或者dp,肯定要开二维,但是还要记录当前的时间,因为你的步数不一定等于时间嘛,你可以停在原地的,所以就要开三维。

所以这是不可以的,然后注意到题上有个信息就是鼹鼠出现时间按照增序给你,那么不妨从鼹鼠下手。
因为每次转移都要清楚上一个鼹鼠的坐标,所以我们必须把当前打的最后一个鼹鼠坐标也好序号也罢给出,

所以就想到了设置f[i]表示到以第i只鼹鼠结尾的打的最多鼹鼠数,如果设置f[i]表示到第i时间打到的最多鼹鼠数还是做不了的。

f[i]=max(f[i],f[j]+1)       然后能不能转移只需要判断曼哈顿距离即可

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{int x,y,t;}a[N];
int n,m,f[N],ans;
int dis(int x,int y,int xx,int yy){return abs(x-xx)+abs(y-yy);
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++)cin>>a[i].t>>a[i].x>>a[i].y;for(int i=1;i<=m;i++){f[i]=1;for(int j=1;j<i;j++)if(dis(a[i].x,a[i].y,a[j].x,a[j].y)<=a[i].t-a[j].t)f[i]=max(f[i],f[j]+1);ans=max(ans,f[i]);	}cout<<ans;
}

        

        

吃吃吃

思路:

一开始我在想:从下往上走

那么我就自下而上的去dp,但是发现这样的话有些点的状态是错误的,然后就特别想去模拟这个dp。
最开始想的是bfs,但是这样的话每个点只能被更新一次,并不能达到正确更新,那么如果借鉴spfa的更新技巧或许可以解决这个问题,于是打出了这篇题解。

#include <bits/stdc++.h>
using namespace std;
int ans,a[300][300],f[300][300];
bool vis[300*300];
struct node{int x,y;};
queue<node>q;
int main(){int m,n;cin>>m>>n;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)cin>>a[i][j];q.push(node{m+1,n/2+1});//一定要注意起点memset(f,-0x3f,sizeof(f));f[m+1][n/2+1]=0;vis[(m+1)*n+n/2+1]=1;//vis表示是否在队列中,有环我们只管走,有spfa别怕while(!q.empty()){node cur=q.front();q.pop();vis[cur.x*n+cur.y]=0;for(int i=-1;i<=1;i++){int tx=cur.x-1,ty=cur.y+i;if(tx<=0||tx>m||ty<=0||ty>n)continue;if(f[tx][ty]<f[cur.x][cur.y]+a[tx][ty]){f[tx][ty]=f[cur.x][cur.y]+a[tx][ty];if(!vis[tx*n+ty])q.push(node{tx,ty}),vis[tx*n+ty]=1;}}}for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)ans=max(ans,f[i][j]);cout<<ans;
}

也是非常高兴啊,然后看了别人的题解,我tm真是想多了,还是可以直接循环dp的,只要你设置好f的意义就可以从上向下dp,然后答案对应的f也很好求出
设置f[i][j]表示以此为起点能获取的最大能量,然后正向dp就行了

f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];

哎呀,也是想到了数字金字塔那道题,确实是一类的(【算法每日一练]-动态规划(保姆级教程 篇14) #三倍经验 #散步 #异或和 #抽奖概率-CSDN博客)

#include<iostream>
#include<cstring>                             //头文件
using namespace std;
int n,m,a[201][201],f[201][201]={0},x,y;
int main()
{cin>>n>>m;y=m/2+1;x=n;                           //求出李大水牛最开始的位置memset(a,-9999,sizeof(a));               //设置边界,为了避免李大水牛吃到餐桌外面去。。for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];               //输入}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];         //动态方程}}cout<<max(max(f[x][y],f[x][y-1]),f[x][y+1])<<endl;       //因为最大值只可能在李大水牛的前方、左前方、右前方,所以只要找这三个的最大就行了return 0;
}

这里也是给各位提一个醒,也是给自己再说一遍:

1,bfs跑图时候一定要把终点也吃进去才能检测到终点

2,如果dp要走环的话,就一定要提前保存cur的dp信息,否则就在循环中被修改,即:
f[tx][ty]=f[cur.x][cur.y]+1,后式在循环中可能就会被当场更新 

        

        

非零字段划分

样例:11
3 1 2 0 0 2 0 4 5 0 2


差分法:
借助岛屿问题来分析此题。我们将一维数组具体成一排的岛屿。最开始p足够大,所有岛屿都被淹没cnt=0
海平面开始逐渐下降,那么慢慢的会有岛屿漏出水面,也会有岛屿合并为一个。
假设当前海平面为i时,高度恰为i的岛峰将会出现cnt++,高度恰为i的岛谷将会出现cnt--。我们不关心岛屿只关心岛峰和岛谷(因为只有这两种才影响答案)
所以我们的任务是预处理出所有的岛谷高度和岛峰高度。最后开始变化。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=1e4;
int a[N+2],d[M+1];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);a[0]=a[n+1]=0;n=unique(a,a+n+2)-a-1;//此时元素大小为n-1,去重便于统计峰和谷for(int i=1;i<n;i++){if(a[i-1]<a[i]&&a[i]>a[i+1])d[a[i]]++;else if(a[i-1]>a[i]&&a[i]<a[i+1])d[a[i]]--;}int ans=0,sum=0;for(int i=M;i>=1;i--)sum+=d[i],ans=max(ans,sum);cout<<ans;
}

这篇关于马上蓝桥杯了,干货总结动态规划专题,祝你考场爆杀(拔高篇)最佳课题选择 书本整理 打鼹鼠 吃吃吃 非零字段划分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/860024

相关文章

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

MyBatis-Plus 自动赋值实体字段最佳实践指南

《MyBatis-Plus自动赋值实体字段最佳实践指南》MyBatis-Plus通过@TableField注解与填充策略,实现时间戳、用户信息、逻辑删除等字段的自动填充,减少手动赋值,提升开发效率与... 目录1. MyBATis-Plus 自动赋值概述1.1 适用场景1.2 自动填充的原理1.3 填充策略

Olingo分析和实践之EDM 辅助序列化器详解(最佳实践)

《Olingo分析和实践之EDM辅助序列化器详解(最佳实践)》EDM辅助序列化器是ApacheOlingoOData框架中无需完整EDM模型的智能序列化工具,通过运行时类型推断实现灵活数据转换,适用... 目录概念与定义什么是 EDM 辅助序列化器?核心概念设计目标核心特点1. EDM 信息可选2. 智能类

Spring Boot 与微服务入门实战详细总结

《SpringBoot与微服务入门实战详细总结》本文讲解SpringBoot框架的核心特性如快速构建、自动配置、零XML与微服务架构的定义、演进及优缺点,涵盖开发环境准备和HelloWorld实战... 目录一、Spring Boot 核心概述二、微服务架构详解1. 微服务的定义与演进2. 微服务的优缺点三

Python自动化批量重命名与整理文件系统

《Python自动化批量重命名与整理文件系统》这篇文章主要为大家详细介绍了如何使用Python实现一个强大的文件批量重命名与整理工具,帮助开发者自动化这一繁琐过程,有需要的小伙伴可以了解下... 目录简介环境准备项目功能概述代码详细解析1. 导入必要的库2. 配置参数设置3. 创建日志系统4. 安全文件名处

Zabbix在MySQL性能监控方面的运用及最佳实践记录

《Zabbix在MySQL性能监控方面的运用及最佳实践记录》Zabbix通过自定义脚本和内置模板监控MySQL核心指标(连接、查询、资源、复制),支持自动发现多实例及告警通知,结合可视化仪表盘,可有效... 目录一、核心监控指标及配置1. 关键监控指标示例2. 配置方法二、自动发现与多实例管理1. 实践步骤

MySQL 迁移至 Doris 最佳实践方案(最新整理)

《MySQL迁移至Doris最佳实践方案(最新整理)》本文将深入剖析三种经过实践验证的MySQL迁移至Doris的最佳方案,涵盖全量迁移、增量同步、混合迁移以及基于CDC(ChangeData... 目录一、China编程JDBC Catalog 联邦查询方案(适合跨库实时查询)1. 方案概述2. 环境要求3.

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

全面掌握 SQL 中的 DATEDIFF函数及用法最佳实践

《全面掌握SQL中的DATEDIFF函数及用法最佳实践》本文解析DATEDIFF在不同数据库中的差异,强调其边界计算原理,探讨应用场景及陷阱,推荐根据需求选择TIMESTAMPDIFF或inte... 目录1. 核心概念:DATEDIFF 究竟在计算什么?2. 主流数据库中的 DATEDIFF 实现2.1

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析