[UOJ#244][UER#7A]短路

Description

你有一个大小为(2n+1)*(2*n+1)的n+1个圈构成的图，下面是n=4的情况。

其中字母相同的点的权值相同。

给出每个点的权值，你可以走到4相邻的格子，求从左上走到右下所经过的点的权值和的最小值。

n<=10^5

Solution

首先，我们可以想到，最优路径一定是只往右\下走的，因为往回走我们可以平移一下，使得某一条边没必要经过。

然后有一个很（不）显然的结论，我们一定经过走到的最深的那一圈的左上角，然后绕到右下角，以相同方向走出去。

如果走中间更优，那么我们完全可以不走最里面那一圈，或者把前面的往下平移到这一圈。

感性理解一下吧。。。

那么现在问题就变成了求从(1,1)走到(i,i)的最短路，贪心一下就好了。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=+;
ll sum,Min,cnt,x[N],ans;
int n;
int main() {
    scanf("%d",&n);Min=;ans=;
    fo(i,,n) scanf("%lld",&x[i]);
    fd(i,n,) {
        sum+=x[i];Min=min(Min,x[i]);
        ans=min(ans,*(sum+cnt)+(ll)(*i-)*x[i]);cnt+=Min;
    }
    printf("%lld\n",ans);
}