【题解】银联挑战赛1A 码队女朋友的王者之路⭐⭐⭐【思维】

【题解】银联挑战赛1A 码队女朋友的王者之路⭐⭐⭐【思维】

银联挑战赛1A 码队女朋友的王者之路

码队的女朋友非常喜欢玩某款手游，她想让码队带他上分。但是码队可能不会带青铜段位的女朋友上分，因为码队的段位太高（已经到达王者），恐怕不能和他的女朋友匹配游戏。

码队的女朋友有些失落，她希望能尽快冲上王者。这个赛季开始了，求胜心切的码队的女朋友想让码队帮她计算一个问题：

这个赛季码队的女朋友一共打了 NN 场排位赛，每一场排位赛中，码队女朋友的成绩用 S_iS
i
​
来表示（成绩只可能为“赢”或“输”。 11 代表码队女朋友赢了这场比赛，00 则代表输了这场比赛）。由于这款游戏使用净胜场数这个数据指标来衡量玩家能否晋级更高的段位（玩家净胜场数 = 玩家赢场数 - 玩家输场数），所以码队的女朋友想知道，这个赛季的过程中她的最高净胜场次。

码队听完他女朋友的问题之后，觉得她有些天真，因为码队知道，这家游戏厂商可能出于不想让玩家早“弃坑”的目的，所以在每个赛季都会给每位玩家发出 KK 张 「排位保护卡」。如果一名玩家在一场排位赛中输掉了游戏，但 TA 还有排位保护卡，那么系统将自动为 TA 用掉一张排位保护卡，帮该玩家抵消这场输掉的排位赛（即在系统记录成绩时，不将该局游戏计入玩家的输场数）。但是，如果一名玩家在某个赛季中，没有用完这 KK 张排位保护卡，那么这些剩余的排位保护卡将失效，不能在下个赛季继续使用。

听完码队说的这些事情以后，码队的女朋友变得更有信心了！现在，码队的女朋友想求助你：如果按照这个赛季的这 NN 场排位赛成绩来计算，经过 MM 个赛季（假设每个赛季都打 NN 场排位赛，且每个赛季都获得了完全相同的排位赛成绩），那在这 MM 个赛季过程中，她的最高净胜是多少场？

Input

第一行一个整数 TT，表示有几组数据（T le 1000T≤1000）。

对于每一组测试数据：第一行有三个整数 N,K,MN,K,M，分别代表码队的女朋友在一个赛季里总共打了 NN 场排位赛，每个赛季有 KK 张排位保护卡，总共将进行 MM 个赛季，以空格分隔。（1le K le N le 1001≤K≤N≤100，1 le M le 10^91≤M≤10 9 ）

接下来一行，输入一个长度为 NN 的字符串（只由 00 和 11 组成），代表码队的女朋友在一个赛季里的每场排位赛中的成绩 S_iS i​ (i=1,2, cdots ,N)(i=1,2,⋯,N)。

Output

对于每一组测试数据，输出一行。

每行只包含一个整数，代表在 MM 个赛季过程中，码队的女朋友最高能净胜多少场游戏。如果净胜场数为负，请输出 00。

Examples

样例输入1 复制
1
5 1 2
11110
样例输出1 复制
8
样例输入2 复制
1
5 2 2
00101
样例输出2 复制
2

题解:

主要是题意比较难理解, 样例又极其误导人, 注意是求出最高净胜场次, 也就是在每轮排位赛结束时的净胜场次+排位赛的最高可净胜场次(还没打完时)
注意特判负值

经验小结:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 1e5+10;int main()
{LL T, n, m, k, cmax = 0, cur = 0;string s;cin >> T;while(T--){cin >> n >> k >> m;cin >> s;cmax = cur = 0;for(LL i = 0; i < s.length(); ++i){if(s[i]=='1'){++cur;}else{if(k > 0)--k;else--cur;}cmax = max(cmax, cur);}if(cur < 0)cout << cmax << endl;elsecout << cur*(m-1)+cmax << endl;}return 0;
}