注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【递归】hdu 3350 #define is unsafe  

2011-11-16 14:05:33|  分类: ACM_其他 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目大意:
你懂的

分析
递归求解,只要想好什么时候递归,什么时候返回就行了,想想编译原理中讲到的一些知识

这个题好恶心啊~

代码:

#include <cstdio>
#include <cstring>

using namespace std;


char data[1010];
int dpos;//全局指针
int len;

struct Node
{
        int value;//值
        int cont;//加法的次数
};

void init()
{
        scanf("%s",data);
        len = strlen(data);
}

int getnum()
{
        char snum[20];
        int i = 0;
        while(data[dpos + i] >= '0' && data[dpos + i] <= '9' && dpos + i < len)
        {
                snum[i] = data[dpos + i];
                i ++;
        }
        snum[i] = '\0';
        dpos += i;
        sscanf(snum,"%d",&i);
        return i;
}


Node dfs()
{
        Node ret;
        ret.value = ret.cont = 0;
        Node rnode;
        rnode.value = rnode.cont = 0;
        Node tnode;
        tnode.value = tnode.cont = 0;
        bool f = false;//标记计算的是MAX(,)中的左节点还是右节点,对于1+2这种情况返回的 时候认为是返回左节点
        int tnum;
        while(1)//有六种情况
        {
                if(data[dpos] == 'M')//如果是MAX(,则进入下一层递归
                {
                        dpos += 4;
                        tnode = dfs();
                        if(!f)//注意这里要这样
                        {
                                ret.value += tnode.value;
                                ret.cont += tnode.cont;
                        }
                        else
                        {
                                rnode.value += tnode.value;
                                rnode.cont += tnode.cont;
                        }
                }
                
                if(data[dpos] == '+')//如果是+,则继续在本层计算
                {
                        if(!f) ret.cont ++;
                        else rnode.cont ++;
                        dpos ++;
                }
                
                if(data[dpos] >= '0' && data[dpos] <= '9')//如果是数字,则继续在本层递归计算
                {
                        tnum = getnum();
                        if(!f)        ret.value += tnum;
                        else rnode.value += tnum;
                }

                if(dpos >= len)//所有字符都处理完的情况
                {
                        return ret;
                }

                if(data[dpos] == ')')//如果是),则返回到上一层中
                {
                        dpos ++;
                        if(!f) return ret;
                        else 
                        {
                                if(ret.value > rnode.value)
                                {
                                        ret.cont = ret.cont * 2 + rnode.cont;
                                }
                                else
                                {
                                        ret.value = rnode.value;
                                        ret.cont = rnode.cont * 2 + ret.cont;
                                }
                                return ret;
                        }
                }
        
                if(data[dpos] == ',')//如果是,则继续在本层,且要修改f
                {
                        f = true;
                        dpos ++;
                }
        }
}



void work()
{
        dpos = 0;
        Node ans;
        ans = dfs();
        printf("%d %d\n",ans.value,ans.cont);
}

int main()
{
        int cas;
        scanf("%d",&cas);
        while(cas --)
        {
                init();
                work();
        }
        return 0;
}

  评论这张
 
阅读(378)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018