题目

“第七套广播体操，原地踏步——走！”
众所周知，跳蚤们最喜欢每天早起做早操，经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点，于是他们打算让炸弹更快地引爆，这样就可以消灭更多早起的跳蚤。
三星 note7 的主板可以看作是由 (2n+1)×(2n+1)(2n+1)×(2n+1) 个中继器构成的，某些中继器会有导线连在一起，左上角和右下角的中继器分别连着电源的正负极。
电流流过一根导线的时间可忽略不计，但当电流经过中继器时，会延缓一段时间再从中继器流出。这个时间只跟该中继器本身有关，我们把这段时间的长度称为中继器的延时值。
这些中继器由导线连接围成一个一个的层，同个层的中继器的种类都一样，而不同层的种类都不一样，可以发现总共有 n+1n+1 层。当 n=4n=4 时，主板大概长这样：

跳晚们打算再加几根导线将某些中继器连接起来.凭借发达的重工业，他们能生产出无数条导线。但由于主板的限制，他们的导线只能和主板四周的边平行，且其长度只够连接相邻两个中继器。
现在他们想知道，他们改造的三星 note7 的电源正极流出的电流能在多短的时间到达电源负极从而造成短路，这样电池就会释放出巨大的能量摧毁跳蚤国的有生力量了。
请参考输入格式和样例配图来更好地理解题意。

分析

结论+贪心题
首先，显然最优值只能是向下或向右走，
设$f_{i}$表示从$(1,1)$走到$(i,i)$的最小值，
那么转移为

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=1000000007;
const long long N=100005;
using namespace std;
long long f[N],n,a[N],mn=2147483647,ans=2147483647;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n+1;i++) scanf("%lld",&a[i]);
    mn*=mn;
    ans*=ans;
    for(int i=n+1;i>=1;i--)
    {
        if(i==n+1) f[i]=a[i];
        else f[i]=f[i+1]+a[i]+mn;
        if(mn>=a[i])
        {
            ans=min(ans,f[i]*2+(4*i-5)*a[i]);
            mn=a[i];
        }
    }
    cout<<ans<<endl;
}

最后

以上就是温暖橘子为你收集整理的【UOJ244】【UER #7】短路题目分析的全部内容，希望文章能够帮你解决【UOJ244】【UER #7】短路题目分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。