思维+线性dp，CF573 B. Bear and Blocks

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 573B - Codeforces

---

二、解题报告

1、思路分析

本题给的图还是很直观的

我们考虑每一列的消失：

上面一个格子消失导致下一个格子下一秒消失——消失时间为当前列格子个数

左边一列消失导致下一秒当前列消失——消失时间为左边列消失时间+1

右边一列消失导致下一秒当前列消失——消失时间为右边列消失时间+1

我们设f[i]为第i列消失所用时间

那么f[i] = min(nums[i], min(f[i - 1] + 1, f[i + 1] + 1))

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

​

import sys
import math
# sys.stdin = open('in.txt', 'r')
 
input = lambda: sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x) + '\n')
 
n = int(input())
 
f = list(map(int, input().split()))
 
f[0] = 1
for i in range(1, n):
    f[i] = min(f[i], f[i - 1] + 1)
f[n - 1] = 1
 
for i in range(n - 2, -1, -1):
    f[i] = min(f[i], f[i + 1] + 1)
 
write(max(f))