【UOJ244】【UOJ #7】短路

57 阅读 0 评论 38 点赞

我是靠谱客的博主谨慎导师，最近开发中收集的这篇文章主要介绍【UOJ244】【UOJ #7】短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

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

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

这些中继器由导线连接围成一个一个的层，同个层的中继器的种类都一样，而不同层的种类都不一样，可以发现总共有 n+1n+1 层。当 n=4n=4 时，主板大概长这样：
这里写图片描述
跳晚们打算再加几根导线将某些中继器连接起来.凭借发达的重工业，他们能生产出无数条导线。但由于主板的限制，他们的导线只能和主板四周的边平行，且其长度只够连接相邻两个中继器。

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

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

###Solution
结论题…

首先显然是只能向右向下走，如果向左向上走的话，我们显然可以省掉上一步。

然后我们先假设走到第 $i$ 层的左上角，然后我们要计算最小代价。那么我们从这层的左上角往左往上走，显然前 $i - 1$ 层都至少被走过一个点，那么我们肯定是从当前前缀最小值所在层 $j (j < i)$ 走 $(i - j + 1)$ 个点，然后中间第 $j + 1$ 到 $i - 1$ 层每层只走一个点，然后再加上走到第 $j$ 层左上角的代价。

于是我们可以顺着推下来，维护前缀最小值和到每层左上角的最小代价。

然后，现在我们要从左上角走到相应层的右下角，计算最小代价，~~那么感性理解一下~~，我们可以得出结论，如果该层是前缀最小值，那么走的路径就是左上角绕一圈到到右下角，如果不是，那么走到左上角~~（就是一个错误的决定）~~就不是最短路径。

于是就是贪心+维护一大堆东西就可以了。

###Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define inf 90000000000000ll
#define N 100001
#define ll long long
using namespace std;
ll a[N];
ll f[N],s[N];
int main()
{
	int n;
	cin>>n;
	n++;
	fo(i,1,n) scanf("%lld",&a[n-i+1]);
	int q=n*2-1;
	ll ans=a[1]*(q*2-1);
	ll mmin=a[1],t=1;
	s[1]=f[1]=a[1];
	fo(i,2,n)
	{
		q-=2;
		s[i]=s[i-1]+a[i];
		f[i]=f[t]+(i-t)*a[t]+s[i]-s[t];
		if(mmin>a[i])
		{
			ll tmp=f[i]*2+a[i]*max(q*2-3,0);
			if(i==n) tmp-=a[i];
			ans=min(ans,tmp);
			mmin=a[i],t=i;
		}
	}
	cout<<ans;
}