首页 > 代码库 > 【UOJ244】[UER7]短路
【UOJ244】[UER7]短路
【题目大意】
(2n+1)*(2n+1)的矩形,由里到外每一层都有一个相同的值。问从左上走到右小经过的点累和的最小值。
【思路】
一眼就是贪心。首先能够想到的是,权值最小的那些边要尽可能夺走,所以必定有一条路要跑完至少两条边。然后我们就可以从右上到左下劈开来,左上和右下是对称的。
假设我们现在要走完从外到里第i层的两条边,现在已经知道了走到第i-1层左上角要走的最短路程,那么要抵达第i层的左上角至少要走多少呢?
显然第i层至少走一格,另外一格就留给当前权值最小的那一层走好了。讲不清楚,意会一下。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int MAXN=1e5+10; 5 const ll INF=1e16; 6 int n; 7 ll a[MAXN]; 8 9 void init() 10 { 11 scanf("%d",&n); 12 for (int i=0;i<=n;i++) scanf("%lld",&a[i]); 13 } 14 15 void solve() 16 { 17 ll ans=INF; 18 ll Min=INF,now=0; 19 for (int i=n;i>=0;i--) 20 { 21 ans=min(ans,now+(4*i+1)*a[i]); 22 Min=min(Min,a[i]); 23 now=now+2*Min+a[i]*2; 24 } 25 printf("%lld",ans); 26 } 27 28 int main() 29 { 30 init(); 31 solve(); 32 }
【UOJ244】[UER7]短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。