【UOJ244】【UER #7】短路

题解：

感觉贪心水平有所提高。。

首先比较显然的事情是我们可以枚举最深进行到哪一层

我们会发现，当且仅当该层是最小值才会使用决策，

并且是从该层的左上，走到右下

另外中间步骤就是（好难描述啊）一个单调下降序列，每个会走最多的向右走的步数，然后中间的点只走一次（这句话应该正常人是无法理解的）

但是处理起来还是比较简单的，我们考虑从上一层到这一层实际上就是有一个多往右走一格，所以维护前缀最小值

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define IL inline

#define rint register ll

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

const ll N=2e5;

const ll INF=1e18;

ll a[N],n,f[N],ans=INF;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  ios::sync_with_stdio(false);

  cin>>n;

  rep(i,,n+) cin>>a[i];

  ll mina=INF;

  dep(i,n+,)

  {

    if (i==n+) f[i]=a[i];

    else f[i]=f[i+]+a[i]+mina;

    if (mina>=a[i])

    {

      ans=min(ans,f[i]*+(*i-)*a[i]);

      mina=a[i];

    }

  }

  cout<<ans<<endl;

  return ;

}

巴特西

【UOJ244】【UER #7】短路

最新文章

热门文章