UOJ244 - [UER 7] 短路

2016/10/18

上周日打的这场比赛。然后炸了!

好吧先说这个第一题:

 C - C - C - C - C
 |   |   |   |   |
 C - B - B - B - C
 |   |   |   |   |
 C - B - A - B - C
 |   |   |   |   |
 C - B - B - B - C
 |   |   |   |   |
 C - C - C - C - C

↑大概这样一个图

求左上到右下的一条路径,使得路径上经过的点权最小。(显而易见的贪心)

首先考虑到这货的对称性,可以沿着它的主对角线劈开,然后在左下这块求解。然后就是考虑要贪的内容了,对于这个图来说权值最小的那层我们是全走的,然后就是写一个递推,把之前做的不够好的决策都平移到这个权值最小的层上。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1E5 + 20;
const int INF   = 0x7f7f7f7f;
const  LL LINF  = 1E16;
LL A[MAX_N]; LL F[MAX_N];
int N;

int main() {
    ios::sync_with_stdio(false);
    cin >> N; N++;
    for(int i=0;i<N;i++) {
        cin >> A[i];
    }

    LL mm = LINF, ans = LINF, now = 0;
    for(int i=N-1;i>=0;i--) {
        ans = min(ans, now + ((i<<2)+1)*A[i]);
        mm  = min(mm, A[i]);
        now += (mm<<1) + (A[i]<<1);
    }

    cout << ans << endl;
}