Valera has array a, consisting of n integers a0,a1,...,an-1, and function f(x), taking an integer from 0 to 2n-1 as its single argument. Value f(x) is calculated by formula , where value bit(i) equals one if the binary representation of number xcontains a 1 on the i-th position, and zero otherwise.
For example, if n=4 and x=11 (11=20+21+23), then f(x)=a0+a1+a3.
Help Valera find the maximum of function f(x) among all x, for which an inequality holds: 0≤x≤m.
Input
The first line contains integer n (1≤n≤105) — the number of array elements. The next line contains n space-separated integersa0,a1,...,an-1 (0≤ai≤104) — elements of array a.
The third line contains a sequence of digits zero and one without spaces s0s1... sn-1 — the binary representation of number m. Numberm equals .
Output
Print a single integer — the maximum value of function f(x) for all .
Sample test(s)
input
2
3 8
10
output
3
input
5
17 0 10 2 1
11010
output
27
Note
In the first test case m=20=1,f(0)=0,f(1)=a0=3.
In the second sample m=20+21+23=11, the maximum value of function equals f(5)=a0+a2=17+10=27.
本文URL地址:http://www.bianceng.cn/Programming/sjjg/201410/45352.htm
思路:从左往右读,读到0就积累,读到1的时候,就看是修改这个1为0然后把前面的0改为1更大,还是不变更大。
修改的话,就从当前这个修改成0的1开始积累。
最终修改结果就是我们想要的x。
完整代码:
/*62ms,500KB*/ #include<cstdio> #include<algorithm> using namespace std; const int maxm = 100005; int a[maxm]; char s[maxm]; int main() { int n, sum, maxn, i; scanf("%d", &n); for (i = 0; i < n; ++i) scanf("%d", &a[i]); getchar(); gets(s); sum = maxn = 0; for (i = 0; i < n; ++i) { if (s[i] & 15) { ///看是前面的一串0大,还是当前位置的1大 if (maxn > a[i]) { sum += maxn; maxn = a[i]; ///重新积累 } else sum += a[i]; } else maxn += a[i];///积累maxn } printf("%d\n", sum); return 0; }
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索function
, 贪心
, integer
, contains
, maximum
, of
The
codeforces、codeforces round 305、codeforces 下载、codeforces round 389、codeforces hack,以便于您获取更多的相关知识。