Contest 2050 and Codeforces Round #718 D. Explorer Space(dp动态规划)

2023-10-30 03:58

本文主要是介绍Contest 2050 and Codeforces Round #718 D. Explorer Space(dp动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目连接:https://codeforces.com/contest/1517/problem/D

You are wandering in the explorer space of the 2050 Conference.

The explorer space can be viewed as an undirected weighted grid graph with size n×m. The set of vertices is {(i,j)|1≤i≤n,1≤j≤m}. Two vertices (i1,j1) and (i2,j2) are connected by an edge if and only if |i1−i2|+|j1−j2|=1.

At each step, you can walk to any vertex connected by an edge with your current vertex. On each edge, there are some number of exhibits. Since you already know all the exhibits, whenever you go through an edge containing x exhibits, your boredness increases by x.

For each starting vertex (i,j), please answer the following question: What is the minimum possible boredness if you walk from (i,j) and goes back to it after exactly k steps?

You can use any edge for multiple times but the boredness on those edges are also counted for multiple times. At each step, you cannot stay on your current vertex. You also cannot change direction while going through an edge.

Input
The first line contains three integers n, m and k (2≤n,m≤500,1≤k≤20).

The j-th number (1≤j≤m−1) in the i-th line of the following n lines is the number of exibits on the edge between vertex (i,j) and vertex (i,j+1).

The j-th number (1≤j≤m) in the i-th line of the following n−1 lines is the number of exibits on the edge between vertex (i,j) and vertex (i+1,j).

The number of exhibits on each edge is an integer between 1 and 106.

Output
Output n lines with m numbers each. The j-th number in the i-th line, answerij, should be the minimum possible boredness if you walk from (i,j) and goes back to it after exactly k steps.

If you cannot goes back to vertex (i,j) after exactly k steps, answerij should be −1.

Examples

input

3 3 10
1 1
1 1
1 1
1 1 1
1 1 1

output

10 10 10
10 10 10
10 10 10

input

2 2 4
1
3
4 2

output

4 4
10 6

input

2 2 3
1
2
3 4

output

-1 -1
-1 -1

分析

将每个方格用其序号表示,(i, j) 即序号 (i - 1) * m + j 。
设 dp[i][j] 表示从第 i 个方格走出去 j 步最少的花费,转移方程为:
dp[i][j] = min(dp[i][j], dp[与 i 相邻的方格][j - 1] + 到每格的花费)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n,m,k;
map<int,int> g[250010];
int dp[250010][15];
int dirx[4]={0,1,0,-1};
int diry[4]={1,0,-1,0};int main(){memset(dp, 0x3f3f3f3f, sizeof(dp));scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n*m;i++) dp[i][0] = 0;for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int x;scanf("%d",&x);int u = (i - 1) * m + j;int v = u + 1;g[u][v] = g[v][u] = x;}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int x;scanf("%d",&x);int u = (i - 1) * m + j;int v = u + m;g[u][v] = g[v][u] = x;}if(k % 2 != 0){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("-1 ");}printf("\n");}return 0;}for(int kk=1;kk<=k/2;kk++)for(int x=1;x<=n;x++)for(int y=1;y<=m;y++){int u,v;u = (x - 1) * m + y;for(int i=0;i<4;i++){int xx = x + dirx[i];int yy = y + diry[i];if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){v = (xx - 1) * m + yy;dp[u][kk] = min(dp[u][kk], dp[v][kk-1] + g[u][v]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int u = (i - 1) * m + j;printf("%d ",dp[u][k/2]*2);}printf("\n");}return 0;
}

这篇关于Contest 2050 and Codeforces Round #718 D. Explorer Space(dp动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/305428

相关文章

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

idea maven编译报错Java heap space的解决方法

《ideamaven编译报错Javaheapspace的解决方法》这篇文章主要为大家详细介绍了ideamaven编译报错Javaheapspace的相关解决方法,文中的示例代码讲解详细,感兴趣的... 目录1.增加 Maven 编译的堆内存2. 增加 IntelliJ IDEA 的堆内存3. 优化 Mave

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...