HDU 5375——Gray code——————【dp||讨论】
Gray code
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 569 Accepted Submission(s): 337
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.
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)
https://en.wikipedia.org/wiki/Gray_code
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=1e5+200;
const int INF=0x3f3f3f3f;
int dp[2*maxn][2];
int a[2*maxn];
char str[2*maxn];
int main(){
int t,cnt=0;
scanf("%d",&t);
while(t--){
scanf("%s",str+1);
int len=strlen(str+1);
for(int i=1;i<=len;i++){
scanf("%d",&a[i]);
dp[i][1]=dp[i][0]=-INF;
}
if(str[1]=='0'){
dp[1][0]=0;
}else if(str[1]=='1'){
dp[1][1]=a[1];
}else{
dp[1][0]=0;
dp[1][1]=a[1];
}
for(int i=2;i<=len;i++){
if(str[i]=='0'){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
}else if(str[i]=='1'){
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
}else {
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]);
}
}
printf("Case #%d: %d\n",++cnt,max(dp[len][1],dp[len][0]));
}
return 0;
}
讨论:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e6+200;
const int INF=0x3f3f3f3f;
char str[2*maxn];
int a[maxn*2];
int main(){
int t,cnt=0;
scanf("%d",&t);
while(t--){
scanf("%s",str);
int len=strlen(str);
for(int i=0;i<len;i++)
scanf("%d",&a[i]);
int sum=0,pos=len,flag=-1;
int i;
for(i=len-1;i>=0;i--){ //逆序处理
if(str[i]=='0'){
if(flag==1){ //如果右边有1
sum+=a[pos];
}
flag=0; //表示当前是0
pos=i;
continue;
}else if(str[i]=='1'){
if(flag==0){
sum+=a[pos];
}
flag=1;
pos=i;
continue;
}else{ //是问号
int num=0,sumv,minv;
if(flag!=-1){
minv=a[pos],sumv=a[pos];
}
else {
minv=INF,sumv=0;
}
int j;
for(j=i;j>=0;j--){
if(str[j]=='0'){
if(flag==1){
if(num%2==1){ //如果问号两边不同,且中间的问号为奇数个,舍弃这段中的最小值
sum+=(sumv-minv);
}else {
sum+=sumv;
}
}else if(flag==0){
if(num%2==1){ //如果两边相同,且中间为奇数个,加上这段所有值
sum+=sumv;
}else{
sum+=(sumv-minv);
} }else{
sum+=sumv;
}
flag=-1;
pos=len;
i=j+1;
break;
}else if(str[j]=='1'){
if(flag==0){
if(num%2==1){
sum+=(sumv-minv);
}else{
sum+=sumv;
}
}else if(flag==1){
if(num%2==0){
sum+=(sumv-minv);
}else{
sum+=sumv;
}
}else{
sum+=sumv;
}
flag=-1;
pos=len;
i=j+1;
break;
}else {
num++;
sumv+=a[j];
if(minv>a[j]){
minv=a[j];
}
}
}
if(j==-1){ //边界处理,比较恶心
i=0;
if(flag==-1 )
sum+=sumv;
else if (flag==1){
if(num%2==0){
sum+= sumv;
}
else sum+=(sumv-minv);
}else {
if(num%2==1){
sum+=sumv;
}else{
sum+=(sumv-minv);
}
}
}
}
}
if(str[0]=='1'&&i==-1){ //字串第一位
sum+=a[0];
}
printf("Case #%d: %d\n",++cnt,sum);
}
return 0;
}
最新文章
- ABP理论学习之审计日志
- Android开源项目分类汇总
- C#并行编程-并发集合
- HDU 1010 Tempter of the Bone (DFS+剪枝)
- 制作滚动视图(ScrollView)
- 模板:优先队列(priority_queue)
- [Unit Testing] Based on input value, spyOn function
- MongoDB的save 和insert函数的区别
- LINUX 学习笔记 账号与群组的管理
- python selenium 处理时间日期控件(十六)
- MyEclipse和eclipse生成变量快捷键
- container injection——容器技术
- Jquery ajax $getScript()和$getJSON和JSONP
- Java -- 异常的捕获及处理 -- 异常类的继承结构
- spring集成shiro报错解决(no bean named &#39;shiroFilter&#39; is defined)
- android 圆角编写(懒得去找,写给自己看的)
- prepareEditor
- [BZOJ1122][POI2008]账本BBB 单调队列+后缀和
- cef开启摄像头和录音
- AssociatedObject关联对象原理实现