【UOJ244】【UER #7】短路（贪心）-白红宇

【UOJ244】【UER #7】短路（贪心）

阅读量：6700 次

发布时间：2019-06-25

本文共 1184 字，大约阅读时间需要 3 分钟。

传送门

Solution

简单题？

考虑一条路径长什么样子，一定是经过某一个字母环的左上角，那么答案就很简单了。

我们记一个前缀最小值，这样子让他一路走下去一定是最优！

然后扫一遍就好了。

代码实现

/*  mail: mleautomaton@foxmail.com  author: MLEAutoMaton  This Code is made by MLEAutoMaton*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}inline ll gl(){ ll f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}ll ans=1e18+10,Min=1e18+10;ll a[400010],sum,n;int main(){ n=gl()+1; for(int i=1;i<=n;i++)a[i]=gl();reverse(a+1,a+n+1); for(int i=1;i<=n;i++) { Min=min(Min,a[i]); ans=min(ans,a[i]*(4*(n-i)+1)+sum*2); sum+=a[i]+Min; } printf("%lld\n",ans); return 0;}