[贪心 + 结论] UOJ244. 【UER #7】短路

需要分析的好题。

显然只需要考虑图的一半,只走右上部分。而且应该是有对称性的,所以只要考虑走到对角线的最小代价。

然后画一画可以发现,每层至少走一次,路径可以往优的层平移,使之更优。

如果有一层 \(i\) 比较优,那一定是越早到越好,是能平移到 \((i,i)\) 位置的。

也就是说,如果一层 \(i\) 走了大于一次,且没有经过 \((i,i)\) ,是没有意义的。

这说明可能的最优路径应该是:

先不断右下走,\((1,1) \to (i_1,i_1) \to (i_2,i_2) \to (i_k,i_k)\) ,然后从 \((i_k,i_k)\) 一直往右走到对角线。

每次新的折点 \((i,i)\) 应该满足 \(\min_{t=1}^{i-1}(a_t) > a_i\) ,即前缀的最小值。

写起来很简单...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
int n,a[maxn],_min=2e9;
LL ans=4e18,sum;
int main(){
freopen("uoj244.in","r",stdin);
freopen("uoj244.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n+1;i++) scanf("%d",&a[i]);
for(int i=n+1;i>=1;i--){
if(i==n+1) sum=a[i]; else sum+=a[i]+_min;
ans=min(ans,(sum+(LL)a[i]*(i*2-2))*2-a[i]);
_min=min(_min,a[i]);
}
printf("%lld\n",ans);
return 0;
}