UOJ #244. 【UER #7】短路贪心+递推

78 阅读 0 评论 52 点赞

我是靠谱客的博主魔幻世界，这篇文章主要介绍UOJ #244. 【UER #7】短路贪心+递推，现在分享给大家，希望可以做个参考。

题目：传送门

分析：在考场上用了将近1h想出了正解，但打的时候打错了，而且也没有去对拍和调试，所以就GG了。
这题正解是贪心。很明显最优解一定是先走到某个矩形的左上角然后走L字形走到右下角然后按照原来的路径走到终点，那么我们可以求出到每个矩形的左上角的最小代价，然后取最优的就好了。
f[i]表示走到从外到里第i个矩形的左上角的最小代价。
f[i]=f[i-1]+mn+a[i];(mn为a[1..i-1]的最小值)

代码：

复制代码

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
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 100015
#define inf 1e+9
using namespace std;

ll a[N],f[N];

int main()
{
    //freopen("uer7A.in","r",stdin);
    //freopen("test.out","w",stdout);
    int n;
    scanf("%d",&n);
    for (int i=n+1;i>=1;i--)
        scanf("%lld",&a[i]);
    f[1]=a[1];
    ll mn=a[1];
    for (int i=2;i<=n+1;i++)
    {
        f[i]=f[i-1]+mn+a[i];
        mn=min(mn,a[i]);
    }
    ll ans=inf*inf;
    for (int i=1;i<=n+1;i++)
        ans=min((f[i]+a[i]*(n*2-i*2+2))*2-a[i],ans);
    printf("%lld",ans);
    return 0;
}