信奥赛-刷题笔记-前缀和篇-T2-P6625卡牌游戏0524

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

前缀和篇题单

P6625 省选联考 2020 B 卷 卡牌游戏

https://www.luogu.com.cn/problem/P6625

题目描述

轩轩某天想到了一个卡牌游戏，游戏规则如下：

1. 初始时轩轩的手中有自左向右排成一排的 n 张卡牌，每张卡牌上有一个整数分值。
2. 接下来，轩轩每次可以选取卡牌序列最左边的连续若干张卡牌（至少 2 张），将它们替换为一张新卡牌。新卡牌将插入到序列的最左端，它的分值为本次操作中被替换掉的卡牌的分值之和。
3. 初始时轩轩总分为 0 ，每执行一次卡牌替换操作，新卡牌的分值将加到总分中。当序列长度为 1 时游戏结束，轩轩也可以在任意时刻结束游戏。

现在给出序列中各个卡牌的分值，请你来帮助轩轩计算他能够获得的最高总分是多少？

输入格式

第一行一个正整数 n ，代表卡牌的数目。

接下来一行 n 个以空格分隔的整数，第 i 个数字 a_i 代表自左向右第 i 张卡牌的分值。

输出格式

仅一行一个整数表示答案。

输入输出样例 #1

输入 #1

3
2 -1 2

输出 #1

4

输入输出样例 #2

输入 #2

7
-4 3 0 7 -3 -5 -3

输出 #2

9

说明/提示

样例解释 1

最优策略为，首先选择最左侧的两张卡牌，总分增加 2 + (-1) = 1 。此时轩轩选择的两张卡牌被替换为一张分值为 1 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 1 和 2 。

接下来选择当前序列中所有卡牌，总分增加 1 + 2 = 3 ，总分为 4 。此时轩轩选择的两张卡牌被替换为一张分值为 3 的卡牌，且被放入序列最左侧，此时序列中只有一张分值为 3 的卡牌，游戏结束。

样例解释 2

最优策略为，首先选择最左侧的四张卡牌，总分增加 (-4) + 3 + 0 + 7 = 6 。此时轩轩选择的四张卡牌被替换为一张分值为6 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 6, -3, -5, -3 。

再选择最左侧的两张卡牌，总分增加 6 + (-3) = 3 ，总分为 9 。此时轩轩选择的两张卡牌被替换为一张分值为3 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 3, -5, -3 。

此时无论如何操作均无法使总分继续增大，轩轩选择结束游戏。

数据范围与约定

测试点 1 \sim6 满足：1\le n\le 16, |a_i| \le 100 。

测试点 7 \sim 12 满足：1\le n\le 10^3, |a_i| \le 100 。

测试点 13 \sim 20 满足：1\le n\le 10^5, |a_i| \le 10^5 。

代码1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ans, x, s, n; // ans: 总得分, x: 当前读入的数, s: 前缀和, n: 卡牌数量

int main() {
    cin >> n;
    
    for (ll i = 1; i <= n; i++) {
        cin >> x;
        s += x;              // 计算前缀和
        if (s > 0 && i != 1) // 只有前缀和 > 0 且不是第一个元素时才加入总得分
            ans += s;
    }
    
    cout << ans;
    return 0;
}

代码2

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;
 
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	cout<<"Hello NOI"<<endl;
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    freopen("7532.in", "r", stdin);
    freopen("7532.out", "w", stdout);
    //原来的代码保持不变
    double a, b, r;
    int k;
    cin >> a >> b;
    k = int(a/b);
    r = a - b * k;
    printf("%g", r);
    //-------------
    fclose(stdin);
    fclose(stdout);
    return 0;
}