1.导论
这道题能不能用贪心做？答案是不能，具体为什么已经有题解给出回答。当贪心无法求解时，我们考虑一下动态规划。
2.算法设计
对于任一节点，其最坏情况（即所需最大起始威力值，后文称最大值）是什么？
当第一个被攻击的怪物（以下称头怪物）在其右边时，其最大值为右边怪物的数量加上自身初始值，头怪物在左边时同理。
因此我们可以考虑\(o(n^2)\)的做法，遍历一遍序列为头节点，再遍历一遍序列找出其余节点对应的最大值即可。
3.算法改进
遗憾的是，n最大达到了\(3\cdot 10^5\)，因此我们要考虑优化程序。
我们发现，任一节点的最大值是由它和头怪物的位置关系决定的。
假设\(a[i]\)为头怪物，其左边节点的最大值为\(r[j],j\in[1,i-1]\),右边节点的最大值为\(l[j],j\in[i+1,n]\)，因此我们可以正序倒序遍历一遍序列，求出每个点作为头怪物时左右节点的最大值。设\(l1[i]\)为左边节点的最大值,\(r1[i]\)为右边节点的最大值。
状态转移方程为：
\(l1[i]=max(l1[i-1],r[i-1])\)
\(r1[i]=max(r1[i+1],l[i+1])\)
4.代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[300005]={0};//代表每个元素的初始值
ll l[300005]={0};//假如头怪物在左边的最坏情况，即左边所有怪物都清空了闪电才劈过来
ll r[300005]={0};
ll l1[300005]={0};//当前怪物为头怪物时，左边的最大值
ll r1[300005]={0};
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
l[i]=a[i]+i-1;
r[i]=a[i]+n-i;
}
ll ans=3e9;
for(int i=1;i<=n;i++) l1[i]=max(l1[i-1],r[i-1]);//由于头怪物在他们的右方，所以左边怪物的最大值等于把右边怪物都清空后的最坏情况
for(int i=n;i>=1;i--) r1[i]=max(r1[i+1],l[i+1]);
for(int i=1;i<=n;i++) ans=min(ans,max(max(l1[i],r1[i]),a[i]));//左边最大值，右边最大值，和自己
cout<<ans;
return 0;
}