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

相关文章

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include