hdu 5375 多校

Gray code

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 604    Accepted Submission(s): 357

Problem Description

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only onebit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical
switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

Now , you are given a binary number of length n including ‘0’ , ’1’ and ‘?’(? means that you can use either 0 or 1 to fill this position) and n integers(a1,a2,….,an) . A certain binary number corresponds to a gray code only. If the ith bit of this gray code
is 1,you can get the point ai.

Can you tell me how many points you can get at most?

For instance, the binary number “00?0” may be “0000” or “0010”,and the corresponding gray code are “0000” or “0011”.You can choose “0000” getting nothing or “0011” getting the point a3 and a4.

Input

The first line of the input contains the number of test cases T.

Each test case begins with string with ‘0’,’1’ and ‘?’.

The next line contains n (1<=n<=200000) integers (n is the length of the string).

a1 a2 a3 … an (1<=ai<=1000)

Output

For each test case, output “Case #x: ans”, in which x is the case number counted from one,’ans’ is the points you can get at most

Sample Input

2
00?0
1 2 4 8
????
1 2 4 8

Sample Output

Case #1: 12
Case #2: 15

Hint

https://en.wikipedia.org/wiki/Gray_code

http://baike.baidu.com/view/358724.htm

Source

2015 Multi-University Training Contest 7

Recommend

wange2014   |   We have carefully selected several similar problems for you:  5379 5378 5377 5376 5375

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cmath>
#include<stdlib.h>
#include<map>
#include<set>
#include<time.h>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1e-8
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef pair<int , int> pii;
#define maxn 200000

int a[maxn];
char s[maxn];
int d[maxn][2];
int n;
int ans;

int main()
{
    int T;
    int kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for(int i = 1; i <= n; i++)
        scanf("%d", a + i);

        for(int i = 0; i <= n; i++)
        d[i][0] = d[i][1] = -INF;

        d[0][0] = 0;
        for(int i = 1; i <= n; i++)
        {
            if(s[i] == '?')
            {
                d[i][0] = max(d[i-1][0], d[i-1][1] + a[i]);
                d[i][1] = max(d[i-1][1], d[i-1][0] + a[i]);
            }
            else
            {
                int t = s[i] - '0';
                d[i][t] = max(d[i-1][t], d[i-1][t^1] + a[i]);
            }
        }
//        for(int i = 0; i <= n; i++)
//        {
//            printf("(%d---%d)\n", d[i][0], d[i][1]);
//        }
        ans = -INF;
        ans = max(d[n][0], d[n][1]);
        printf("Case #%d: %d\n", ++kase, ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-12

hdu 5375 多校的相关文章

HDU 5375(2015多校7)-Gray code(dp)

题目地址:HDU 5375 题意:给你一个二进制串,带'?'的位置可以由你来决定填'1'还是'0',补充完整之后转换成格雷码表示,每一个位置都有一个权值a[i],只有格雷码为'1'的位可以加上权值,问你最终权值之和最大为多少. 思路:首先要明白二进制码和格雷码是如何转换的: dp[i][0]表示第i位为0的时候的最大值,dp[i][1]表示第i位为1的时候的最大值.对于第i位的最大值由dp[i-1][0],dp[i-1][1]和当前权值a[i]得到.当前的位的二进制码有0,1,?三种情况,所以就

hdu 5375 Gray code(DP)

hdu 5375 Gray code Problem Description The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only onebit (binary digit). The reflected binary code was originally designed

hdu 4893 (多校1007)Wow! Such Sequence!(线段树&amp;二分&amp;思维)

Wow! Such Sequence! Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 352    Accepted Submission(s): 104 Problem Description Recently, Doge got a funny birthday present from his new friend, Prot

hdu 5344 (多校联赛) MZL&#39;s xor --- 位运算

here:    首先看一下题吧:题意就是让你把一个序列里所有的(Ai+Aj) 的异或求出来.(1<=i,j<=n) Problem Description MZL loves xor very much.Now he gets an array A.The length of A is n.He wants to know the xor of all (Ai+Aj)(1≤i,j≤n) The xor of an array B is defined as B1 xor B2...xor B

HDU 4915 多校5 Parenthese sequence

比赛的时候想了一个自认为对的方法,WA到死,然后还一直敲下去,一直到晚上才想到反例 找是否存在解比较好找,这种左右括号序列,把(当成1,把)当成-1,然后从前往后扫,+1或者-1 遇到?就当初(,然后如果扫到最后 中间没有出现负数说明左括号没问题 然后同样的方法从后往前扫,判断右括号那里是不是有问题即可.都没问题就有解,否则无解 当然应该要先判断下序列长度是不是偶数,奇数肯定是无解 至于为什么要像之前的处理即可判断有无解,首先只有正好走完的时候 和值为0才是真正合法(因为这个时候左右括号都对应了

HDU 4866 多校1 主席树+扫描线

终于是解决了这个题目了 不过不知道下一次碰到主席树到底做不做的出来,这个东西稍微难一点就不一定能做得出 离散化+扫描线式的建树,所以对于某个坐标二分找到对应的那颗主席树,即搜索出结果即可(因为是扫描线式的建树,找到对应的树之后,就知道该点上面的线段有多少条了) 其他就是普通主席树的操作了 主席树里面维护两个东西,一个就是普通的那种在该区间的节点数目,另外就是权值 #include <iostream> #include <cstdio> #include <cstring&g

HDU 5375 Gray code (简单dp)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5375 题面: Gray code Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 626    Accepted Submission(s): 369 Problem Description The reflected binary cod

HDU 5319多校 模拟

Problem Description Mr. Hdu is an painter, as we all know, painters need ideas to innovate , one day, he got stuck in rut and the ideas dry up, he took out a drawing board and began to draw casually. Imagine the board is a rectangle, consists of seve

HDU 5358 多校第6场 First One

First One Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 672    Accepted Submission(s): 193 Problem Description soda has an integer array . Let  be the sum of . Now soda wants to know the va