题目描述
码队的女朋友非常喜欢玩某款手游，她想让码队带他上分。但是码队可能不会带青铜段位的女朋友上分，因为码队的段位太高（已经到达王者），恐怕不能和他的女朋友匹配游戏。
码队的女朋友有些失落，她希望能尽快冲上王者。这个赛季开始了，求胜心切的码队的女朋友想让码队帮她计算一个问题：
这个赛季码队的女朋友一共打了 N 场排位赛，每一场排位赛中，码队女朋友的成绩用 Si 来表示（成绩只可能为“赢”或“输”。 1 代表码队女朋友赢了这场比赛，0 则代表输了这场比赛）。由于这款游戏使用净胜场数这个数据指标来衡量玩家能否晋级更高的段位（玩家净胜场数 = 玩家赢场数 - 玩家输场数），所以码队的女朋友想知道，这个赛季的过程中她的最高净胜场次。
码队听完他女朋友的问题之后，觉得她有些天真，因为码队知道，这家游戏厂商可能出于不想让玩家早“弃坑”的目的，所以在每个赛季都会给每位玩家发出 K 张 「排位保护卡」。如果一名玩家在一场排位赛中输掉了游戏，但 TA 还有排位保护卡，那么系统将自动为 TA 用掉一张排位保护卡，帮该玩家抵消这场输掉的排位赛（即在系统记录成绩时，不将该局游戏计入玩家的输场数）。但是，如果一名玩家在某个赛季中，没有用完这 K 张排位保护卡，那么这些剩余的排位保护卡将失效，不能在下个赛季继续使用。
听完码队说的这些事情以后，码队的女朋友变得更有信心了！现在，码队的女朋友想求助你：如果按照这个赛季的这 N 场排位赛成绩来计算，经过 M 个赛季（假设每个赛季都打 N 场排位赛，且每个赛季都获得了完全相同的排位赛成绩），那在这 M 个赛季过程中，她的最高净胜是多少场？
输入格式
第一行一个整数 T，表示有几组数据（T≤1000）。
对于每一组测试数据：第一行有三个整数 N,K,M，分别代表码队的女朋友在一个赛季里总共打了 N 场排位赛，每个赛季有 K 张排位保护卡，总共将进行 M 个赛季，以空格分隔。（1≤K≤N≤100，1≤M≤109）
接下来一行，输入一个长度为 N 的字符串（只由 0 和 1 组成），代表码队的女朋友在一个赛季里的每场排位赛中的成绩 Si (i=1,2,⋯,N)。
输出格式
对于每一组测试数据，输出一行。
每行只包含一个整数，代表在 M 个赛季过程中，码队的女朋友最高能净胜多少场游戏。如果净胜场数为负，请输出 0。
输出时每行末尾的多余空格，不影响答案正确性
样例输入1
11
25 1 2
311110
样例输出1
18
样例输入2
11
25 2 2
300101
样例输出2
12
一个普通的模拟，跑第一遍，遇到失败优先使用保护卡。
记录过程中出现的最大值和跑完一遍后的结果
如果结果大于0，那么每过一个赛季，最后的净胜场数都会增加，峰值为最后一个赛季的最大值。
如果结果小于0，那么每过一个赛季，最后的净胜场数都会减少，峰值为第一个赛季的最大值。
建立二维坐标系，横坐标为比赛场数，纵坐标为净胜场数。画个曲线便很容易理解。
Code
1/**
2 * author: Akvicor
3 * created: 2019-07-20 14-06-17
4**/
5
6#include <bits/stdc++.h>
7
8using namespace std;
9
10#ifdef DEBUG
11string to_string(string s) {
12 return '"' + s + '"';
13}
14
15string to_string(const char* s) {
16 return to_string((string) s);
17}
18
19string to_string(bool b) {
20return (b ? "true" : "false");
21}
22
23template <typename A, typename B>
24string to_string(pair<A, B> p) {
25 return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
26}
27
28template <typename A>
29string to_string(A v) {
30 bool first = true;
31 string res = "{";
32 for (const auto &x : v) {
33 if (!first) {
34 res += ", ";
35 }
36 first = false;
37 res += to_string(x);
38 }
39 res += "}";
40 return res;
41}
42
43void debug_out() { cerr << endl; }
44
45template <typename Head, typename... Tail>
46void debug_out(Head H, Tail... T) {
47 cerr << " " << to_string(H);
48 debug_out(T...);
49}
50#endif
51
52#ifdef DEBUG
53#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
54#else
55#define debug(...) 17
56#endif
57
58#ifdef DEBUG
59#define FAST_IO 17
60#else
61#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
62#define endl '\n'
63#endif
64
65#define LL long long
66#define ULL unsigned long long
67#define rep(i, n) for(int i = 0; i < (n); ++i)
68#define reep(i, n) for(int i = 0; i <= (n); ++i)
69#define lop(i, a, n) for(int i = a; i < (n); ++i)
70#define loop(i, a, n) for(int i = a; i <= (n); ++i)
71#define ALL(v) (v).begin(), (v).end()
72#define PB push_back
73#define VI vector<int>
74#define PII pair<int,int>
75#define FI first
76#define SE second
77#define SZ(x) ((int)(x).size())
78
79const double EPS = 1e-6;
80const double PI = acos(-1.0);
81const int INF = 0x3f3f3f3f;
82const LL LINF = 0x7f7f7f7f7f7f7f7f;
83const int MAXN = (int)1e6 + 10;
84const int MOD = (int)1e9 + 7;
85
86int t, n, k, m;
87
88int main(){
89 FAST_IO;
90
91 LL ans = 0;
92 cin >> t;
93 while(t--){
94 cin >> n >> k >> m;
95 string s;
96 ans = 0;
97 cin >> s;
98 LL cnt = 0;
99 for(auto &i : s){
100 if(i=='1') ++ans;
101 else if(i=='0'){
102 if(k){
103 --k;
104 }else{
105 --ans;
106 }
107 }
108 cnt = max(ans, cnt);
109 }
110 if(ans > 0){
111 cout << ans*(m-1) + cnt << endl;
112 }else{
113 cout << cnt << endl;
114 }
115 }
116
117 return 0;
118}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。