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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章