[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=1e5+5;
ll sum,Min,cnt,x[N],ans;
int n;
int main() {
    scanf("%d",&n);Min=0x7fffffff;ans=1e15;
    fo(i,0,n) scanf("%lld",&x[i]);
    fd(i,n,0) {
        sum+=x[i];Min=min(Min,x[i]);
        ans=min(ans,2*(sum+cnt)+(ll)(4*i-1)*x[i]);cnt+=Min;
    }
    printf("%lldn",ans);
}

最后

以上就是糟糕火最近收集整理的关于[UOJ#244][UER#7A]短路的全部内容，更多相关[UOJ#244][UER#7A]短路内容请搜索靠谱客的其他文章。