Alice and Bob play a game. They have a binary string s (a string such that each character in it is either 0 or 1). Alice moves first, then Bob, then Alice again, and so on.
During their move, the player can choose any number (not less than one) of consecutive equal characters in s and delete them.
For example, if the string is 10110, there are 6 possible moves (deleted characters are bold):
10110→0110; 10110→1110; 10110→1010; 10110→1010; 10110→100; 10110→1011. After the characters are removed, the characters to the left and to the right of the removed block become adjacent. I. e. the following sequence of moves is valid: 10110→100→1.
The game ends when the string becomes empty, and the score of each player is the number of 1-characters deleted by them.
Each player wants to maximize their score. Calculate the resulting score of Alice.
Input The first line contains one integer T (1≤T≤500) — the number of test cases.
Each test case contains exactly one line containing a binary string s (1≤|s|≤100).
Output For each test case, print one integer — the resulting score of Alice (the number of 1-characters deleted by her).
Example Input 5 01111001 0000 111111 101010101 011011110111 Output 4 0 6 3 6 Note Questions about the optimal strategy will be ignored. 问第一个人能选取最长的连续的1，将所有连续的1的长度排好序，每次跳着取累加
#include<stdio.h> #include<string.h> #include<math.h> #include<map> #include<stack> #include<set> #include<queue> #include<vector> #include<stdlib.h> #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cstdlib> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; const int maxn=5e4+5; int a[maxn],b[maxn]; int cmp(int x,int y){ return x>y; } int main() { int n; cin>>n; while(n--){ string s; cin>>s; int len=s.length(); int t=1; int maxx=0; memset(b,0,sizeof(b)); for(int i=0;i<len;i++){ if(s[i]=='1'){ b[t]++; } else { t++; } } sort(b+1,b+t+1,cmp); int sum=0; for(int i=1;i<=t;i+=2) sum+=b[i]; cout<<sum<<endl; } return 0; }