本文主要是介绍Codeforces Round #205 (Div. 2) C. Find Maximum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C. Find Maximumtime limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 x contains 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 integers a0, 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. Number m 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.
这题，其实，我们知道，尽可能的多的数是最好的，如果当前位是１的话，我们把这一位换成０下面的全是１，这样，循环，就一定能找到最大值了！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define M 100500
int pri[M],sum[M];
char str[M];
int main()
{int n,i;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){scanf("%d",&pri[i]);sum[i]=i?sum[i-1]+pri[i]:pri[i];}scanf("%s",str);int strnum=strlen(str);int j=strnum-1;while(j>0&&str[j]=='0'){j--;}strnum=j;int ans=0,len=0;for(i=j;i>=0;i--){if(str[i]!='0'){ans=max(ans,len+sum[i-1]);len+=pri[i];}}ans=max(ans,len);cout<<ans<<endl;}return 0;
}
这篇关于Codeforces Round #205 (Div. 2) C. Find Maximum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
