AtCoder ABC周赛2023 1/14 (Sun) D题题解

发布时间:2024年01月21日

原题截图:

主要思路:

这个题目是一道dp题。

可以将金字塔的“一上一下”拆开考虑,最后合并。

以下分析“一上”的情况:

可以发现,若某一区间[l,r]可以作为一个“一上”,则对任意[l,r]中间的点x,[x,r]都可
以作为“一上”。
由此,可以设计dp,设f[i]表示以i为右端点,与左边组成的最长的“一上”是多少,对
于当前节点i,从i-1转移过来,如果要直接不损失拼上去,那对当前a[i]的要求至少是
f[i-1]+1,若a[i]不够,则只能将前面削去一截,直到a[i]-1,然后把a[i]拼上去。于是有
dp方程:f[i]=min(f[i-1]+1,a[i])。
同理,再反方向dp一次,得到“一下”,设dp数组为g[i]。
dp方程:g[i] = min(f[i+1]+1,a[i])
还要循环反过来
最后合并:
ans = \max(ans,min(f_i,g_i))
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010];
int f[200010];
int g[200010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		f[i]=min(f[i-1]+1,a[i]);//dp
	}
	for(int i=n;i>=1;i--)
	{
		g[i]=min(g[i+1]+1,a[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans = max(min(f[i],g[i]),ans);
	}
	cout<<ans;
	return 0;
}

文章来源:https://blog.csdn.net/a613322/article/details/135731414
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。