UOJ244 【UER #7】短路题解

题意：

“第七套广播体操，原地踏步——走！”

众所周知，跳蚤们最喜欢每天早起做早操，经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点，于是他们打算让炸弹更快地引爆，这样就可以消灭更多早起的跳蚤。

三星 note7 的主板可以看作是由 \((2n + 1) \times (2n + 1)\) 个中继器构成的，某些中继器会有导线连在一起，左上角和右下角的中继器分别连着电源的正负极。

电流流过一根导线的时间可忽略不计，但当电流经过中继器时，会延缓一段时间再从中继器流出。这个时间只跟该中继器本身有关，我们把这段时间的长度称为中继器的延时值。

这些中继器由导线连接围成一个一个的层，同个层的中继器的种类都一样，而不同层的种类都不一样，可以发现总共有 \(n + 1\) 层。当 \(n = 4\) 时，主板大概长这样：

跳晚们打算再加几根导线将某些中继器连接起来. 凭借发达的重工业，他们能生产出无数条导线。但由于主板的限制，他们的导线只能和主板四周的边平行，且其长度只够连接相邻两个中继器。

现在他们想知道，他们改造的三星 note7 的电源正极流出的电流能在多短的时间到达电源负极从而造成短路，这样电池就会释放出巨大的能量摧毁跳蚤国的有生力量了。

请参考输入格式和样例配图来更好地理解题意。

输入格式：

第一行一个正整数 \(n\)。

第二行 \(n + 1\) 个正整数 \(a_0, a_1, \dots, a_n\)，表示从内到外每层的中继器的延时值，单位为秒。其中，第 \(i\) 行第 \(j\) 列的中继器的延时值为（\(1 \le i, j \le n\)）

\[ a_{\max(\left|i-n-1\right|,\left|j-n-1\right|)} \] 输出格式：

输出一行一个数表示改造后的最短引爆时间。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

答案肯定是走到某一个矩形的左上角，然后沿着这个矩形再走到终点

至于选择哪个矩形以及怎么最小化走到这个矩形的距离

注意到这个矩形很有递归的性质，因此考虑dp

设 \(f_i\) 表示走到矩形 \(i\) （从外往内依次为 \(0,1,2,\dots\) ）的最小花费，则 \[ f_i = f_{i-1} + \min_{1\le j <i} \{a_j\} \] 边界为 \(f_0 = a_0\) 。转移方程后面那个 \(\min\) 意味着走到 \(i-1\) 的路线在最小花费的地方往下走一格

不难发现这样走一定是最优的。

最后的答案为 \[ \min_{0 \le i \le n}\left\{2\times[f_i + (2n-2i) \times a_i] - a_i\right\} \] 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

int n,num,ans,a[N],f[N];
void down(int &x,int y) { x > y ? x = y : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; num=ans=INF;
    for(int i=n; i>=0; i--) cin >> a[i];
    f[0] = a[0]; num = a[0];
    for(int i=1; i<=n; i++)
    {
        f[i] = f[i-1] + a[i] + num;
        down(num, a[i]);
    }
    for(int i=0; i<=n; i++)
        down(ans, (f[i] + (n*2-i*2)*a[i])*2 - a[i]);
    cout << ans << '\n';
    return 0;
}