Post Lamps CodeForces - 990E（暴力出奇迹？）

题意：

　　在一个从0开始的连续区间上放置几个小区间，使得这些小区间覆盖整个大区间，不同长度的小区间有不同的花费，其中有m个点，小区间的左端点不能放在这些点上

解析：

　　显然如果0是这m点中的一个则无解

　　然后就是标记上连续不能放的点然后遍历每一个小区间从0开始放求花费最小值即可

·　　注意最大值的设置

　　代码都加了1，从1开始

#include <bits/stdc++.h>

using namespace std;

const int maxn = , INF = 0x7fffffffffffffff;;

typedef long long LL;

int vis[maxn], hip[maxn];

LL cost[maxn];

int main()

{

    int n, m, k, tmp;

    scanf("%d%d%d", &n, &m, &k);

    n++;

    for(int i=; i<m; i++)

    {

        scanf("%d", &tmp);

        vis[tmp+] = ;

    }

    if(vis[])

    {

        printf("-1\n");

        return ;

    }

    for(int i=; i<=k; i++)

        scanf("%lld", &cost[i]);

    for(int i=; i<=n; i++)

    {

        if(vis[i])

            hip[i] = hip[i-];

        else

            hip[i] = i;

    }

    LL res = LLONG_MAX;

    for(int i=; i<=k; i++)

    {

        int p = ;

        LL sum = ;

        while()

        {

            if(p + i >= n)

            {

                LL ans = sum * cost[i];

                res = min(res, ans);

                break;

            }

            if(p == hip[p+i])

                break;

            p = hip[p+i];

            sum++;

        }

    }

    if(res == LLONG_MAX)

        printf("-1\n");

    else

        printf("%lld\n", res);

    return ;

}

巴特西

Post Lamps CodeForces - 990E（暴力出奇迹？）

最新文章

热门文章