本文主要是介绍Codeforces Round #205 (Div. 2) / 353C Find Maximum (贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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.
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 
.
Print a single integer — the maximum value of function f(x) for all 
.
2 3 8 10
3
5 17 0 10 2 1 11010
27
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.
思路：从左往右读，读到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;
}
这篇关于Codeforces Round #205 (Div. 2) / 353C Find Maximum (贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
