Codeforces Round #205 (Div. 二) / 353C Find Maximum (贪心)

Codeforces Round #205 (Div. 2) / 353C Find Maximum (贪心)
C. Find Maximumhttp://codeforces.com/problemset/problem/353/C
time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Valera has array a, consisting of n integers a_{0,?a1,?...,?an?-?1, and function f(x), taking an integer from 0 to 2^{n?-?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?=?2^{0?+?21?+?23), then f(x)?=?a_0?+?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?≤?10^{5) — the number of array elements. The next line contains n space-separated integersa_{0,?a1,?...,?an?-?1 (0?≤?ai?≤?104) — elements of array a.}}

The third line contains a sequence of digits zero and one without spaces s_{0s1... sn?-?1 — the binary representation of number m. Numberm equals .}

Print a single integer — the maximum value of function f(x) for all .

23 810

3

517 0 10 2 111010

27

In the first test case m?=?2^{0?=?1,?f(0)?=?0,?f(1)?=?a_0?=?3.}

In the second sample m?=?2^{0?+?21?+?23?=?11, the maximum value of function equals f(5)?=?a_{0?+?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;}