dp小兰走迷宫

news/2024/6/22 12:24:30

昨天学习了bfs的基本概念,今天来做一道经典习题练练手吧! 

 bfs常用的两类题型

1.从A出发是否存在到达B的路径(dfs也可)

2.从A出发到B的最短路径(数小:<20才能用dfs) 

遗留的那个问题的答案-

题目:走迷宫 

 

#include <iostream>
using namespace std;int n;
const int N=1005;
int a[N][N];
typedef long long ll;
ll dp[N][N][2];void solve(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j][0]=-1;dp[i][j][1]=-1;}}dp[1][1][0]=a[1][1];dp[1][1][1]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1)continue;if(a[i][j]==-1||(dp[i-1][j][0]==-1&&dp[i][j-1][0]==-1)){dp[i][j][0]=-1;dp[i][j][1]=-1;continue;}dp[i][j][0]=max(dp[i-1][j][0],dp[i][j-1][0])+a[i][j];ll c1=dp[i-1][j][0]/(i+j-2)*a[i][j];ll c2=dp[i][j-1][0]/(i+j-2)*a[i][j];ll m1=max(c1+dp[i-1][j][0],c2+dp[i][j-1][0]);ll m2=max(dp[i-1][j][1]+a[i][j],dp[i][j-1][1]+a[i][j]);dp[i][j][1]=max(m1,m2);}}cout<<max(dp[n][n][0],dp[n][n][1]);
} 
int main()
{// 请在此输入您的代码ios::sync_with_stdio(0);cin.tie(0);int num=1;while(num--)solve();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

Unity核心学习

目录 认识模型的制作流程模型的制作过程 2D相关图片导入设置图片导入概述纹理类型设置纹理形状设置纹理高级设置纹理平铺拉伸设置纹理平台打包相关设置 SpriteSprite Editor——Single图片编辑Sprite Editor——Multiple图片编辑Sprite Editor——Polygon图片编辑SpriteRendere…

零基础 HTML 入门(详细)

目录 1.简介 1.1 HTML是什么? 1.2 HTML 版本 1.3 通用声明 2.HTML 编辑器 3.标签的语法 4.HTML属性 5.常用标签 5.1 head 元素 5.1.1 title 标签 5.1.2 base 标签 5.1.3 link 标签 5.1.4 style 标签 5.1.5 meta 标签 5.1.6 script 5.2 HTML 注释 5.3 段落标签…

如何转行成为产品经理?

转行NPDP也是很合适的一条发展路径&#xff0c;之后从事新产品开发相关工作~ 一、什么是NPDP&#xff1f; NPDP 是产品经理国际资格认证&#xff0c;美国产品开发与管理协会&#xff08;PDMA&#xff09;发起的&#xff0c;是目前国际公认的唯一的新产品开发专业认证&#xff…

javaWeb网上零食销售系统

1 绪 论 目前&#xff0c;我国的网民数量已经达到7.31亿人&#xff0c;随着互联网购物和互联网支付的普及&#xff0c;使得人类的经济活动进入了一个崭新的时代。淘宝&#xff0c;京东等网络消费平台功能的日益完善&#xff0c;使得人们足不出户就可以得到自己想要的东西。如今…

利用Sentinel解决雪崩问题(一)

1、解决雪崩问题的常见方式有四种: 超时处理:设定超时时间&#xff0c;请求超过一定时间没有响应就返回错误信息&#xff0c;不会无休止等待;舱壁模式:限定每个业务能使用的线程数&#xff0c;避免耗尽整个tomcat的资源&#xff0c;因此也叫线程隔离;熔断降级:由断路器统计业务…

探索进程控制第一弹(进程终止、进程等待)

文章目录 进程创建初识fork函数fork函数返回值fork常规用法fork调用失败的原因 写时拷贝进程终止进程终止是在做什么&#xff1f;进程终止的情况代码跑完&#xff0c;结果正确/不正确代码异常终止 如何终止 进程等待概述进程等待方法wait方法waitpid 进程创建 初识fork函数 在…