AcWing4786.闯关-创新互联

AcWing 4786. 闯关

目前创新互联已为成百上千家的企业提供了网站建设、域名、虚拟主机、网站托管、服务器租用、企业网站设计、旌德网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

某综艺频道推出了一个闯关活动。

活动一共包含 n 个关卡(编号 1∼n),其中 m 个关卡为特殊关卡。

每个关卡都有一个通关分数,其中第 i 个关卡的通关分数为 ai。

挑战者可以自由决定所有关卡的具体挑战顺序,并且每通过一个关卡就可以获得该关卡的通关分数。

值得注意的是,当挑战者即将挑战的关卡是特殊关卡时,如果挑战者当前已经获得的总分数大于该特殊关卡的通关分数,则挑战者可以对该关卡的通关分数进行一次修改,修改后的新分数不能小于原分数,也不能大于挑战者当前已经获得的总分数。

请你计算并输出挑战者通过所有关卡获得的总分数的大可能值。

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数 a1,a2,…,an,表示每个关卡的通过分数。

第三行包含 m 个整数 b1,b2,…,bm,表示每个特殊关卡的编号。

输出格式
一个整数,表示挑战者通过所有关卡获得的总分数的大可能值。

保证最终答案不超过 264−1。

数据范围
前 4 个测试点满足 1≤n≤4。
所有测试点满足 1≤n,m≤100,m≤min(n,30),1≤ai≤107,1≤bi≤n,bi 两两不同。

输入样例1:

4 1
1 3 7 5
3

输出样例1:

18

输入样例2:

3 2
10 3 8
2 3

输出样例2:

40

输入样例3:

2 2
100 200
1 2

输出样例3:

400

输入样例4:

1 1
1
1

输出样例4:

1
题意:
  • 题意:一共n个关卡,m个特殊关卡,挑战者可以自由选择挑战关卡
  • 挑战特殊关卡时,如果挑战者当前分数大于当前关卡,挑战者可以修改当前关卡的分数,
  • 修改要求为 分数大于原来关卡,但小于当前分数
  • 求挑战者可能获取的最高分
题解:
  • 代码解释
    首先用数组a记录各个关卡分数,数组b记录特殊关卡分数,布尔数组st记录是否为特殊关卡
    思路:先将非特殊关卡相加,再将特殊关卡数组从大到小排序(以获取总分数的大值)
代码:
#include#include#include 

using namespace std;

typedef long long LL;

const int N = 110;
LL a[N],b[N];
bool st[N];

LL n,m;
LL res = 0;

int main()
{cin >>n >>m;
    for(int i = 1;i<= n;i++) 
    {cin >>a[i];
        st[i] = true;
    }
    
    for(int i = 1;i<= m;i++)
    {int x;
        cin >>x;
        st[x] = false;      // 记录该关卡为特殊关卡
        b[i] = a[x];        // 将该关卡的分数存到数组b中
    }
    
    sort(b + 1, b + m + 1, greater());  // 从大到小排序特殊关卡
    
    for(int i = 1;i<= n;i++) 
    {if(st[i]) res += a[i];      // 先将非特殊关卡的分数相加
    }
    
    if(m == n)         // 若全部为特殊关卡
    {res = b[1];    
        for(int i = 2;i<= m;i++) res = res * 2;  // 由于数组b倒序,所有后面的关卡分数都可以调为分数总和
    }
    else
    {for(int i = 1;i<= m;i++)
        {if(res< b[i]) res = res + b[i];  // 存在特殊关卡的分数大于当前分数总和,则直接加上该关卡
            else res = res * 2;
        }
    }
    
    cout<< res<< endl;   // 输出可能获得的大分数

    return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章题目:AcWing4786.闯关-创新互联
文章路径:http://scyanting.com/article/ddcdjs.html