正题

题目链接:http://uoj.ac/problem/244

---

题目大意

$n+1$个矩阵如下图所示

每一层的格子有相同的延时，现在加一些平行于坐标轴的导线，求左上到右下的最小延迟。

---

解题思路

可以知道最优解一点是走到某个矩阵的左上角然后走这个矩阵到右下角然后到终点。

设$f_i$表示走到$i$的左上角的最小延迟，显然有$$f_i=f_{i-1}+min\{a_j\}(1\le j<i)$$

递推即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; ll n,a[N],f[N],num,ans; int main() {scanf("%lld",&n);num=ans=1e19;for(ll i=n;i>=0;i--)scanf("%lld",&a[i]);f[0]=a[0];num=a[0];for(ll i=1;i<=n;i++){f[i]=f[i-1]+a[i]+num;num=min(num,a[i]);}for(ll i=0;i<=n;i++)ans=min(ans,(f[i]+(n*2-i*2)*a[i])*2-a[i]);printf("%lld",ans); }

总结

以上是生活随笔为你收集整理的UOJ#244-[UER#7]短路【贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。