【题目大意】
(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 }
原文：http://www.cnblogs.com/iiyiyi/p/5971520.html