CF#537 C. Creative Snap /// DFS

题目大意：

给定n k A B为位置长度复仇者个数两种花费

在一段为1~2^n的位置中某些位置存在一些复仇者

求消灭所有复仇者的最小花费

对一段位置可以有两种处理方式

1.若该段长度至少为2 可以将其分成长度相等的两段分开处理

2.若该段中不存在复仇者那么一共只需花费 A

若该段中存在复仇者那么花费为复仇者个数*该段长度*B

将复仇者位置排序后对范围[l,r]的一段利用二分函数就可获得该段中复仇者的个数

对整段[1,2^n]深搜一下复杂度不超过O((2^n)<<2)

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LL long long

#define mem(i,j) memset(i,j,sizeof(i))

const int N=1e5+;

LL n,k,A,B,a[N];

LL dfs(int l,int r) {

    int L=lower_bound(a,a+k,l)-a;

    int R=upper_bound(a,a+k,r)-a;

    LL cnt=R-L; // 在l r范围内的复仇者的个数

    if(cnt==) return A; // 没有复仇者

    if(l==r) return B*cnt; // 已经缩小到一个点 且该点有复仇者

    int m=(l+r)>>; // 将当前段二分

    return min(B*cnt*(r-l+),dfs(l,m)+dfs(m+,r));

    // 直接消灭整段的复仇者 和 二分后再消灭 取小

}

int main()

{

    while(~scanf("%I64d%I64d%I64d%I64d",&n,&k,&A,&B)) {

        for(int i=;i<k;i++) scanf("%I64d",&a[i]);

        sort(a,a+k); // 将所有复仇者的位置排序 然后才可用二分函数

        printf("%I64d\n",dfs(,<<n));

    }

    return ;

}

巴特西

CF#537 C. Creative Snap /// DFS

最新文章

热门文章