内存:128  时间:1

题目描述

小明陷入一个充满陷阱的密道之中,现在他要逃脱这里!到达密道的出口即可离开这处绝境!
现在给你小明出现在密道中的位置,还有出口的位置。而密道中每一个位置都有陷阱或者血瓶。遇到陷阱会减少生命值,遇到血瓶会增加你的生命值(包含出口)。每一个陷阱或者血瓶减少或着增加的生命值都是不确定的。
小明一次可以走一步或者两步或者三步。
另外小明还有一个神奇的技能,他可以瞬间跳过N个位置!
这个天赋技能的内容具体是这样的:小明可以从当前位置的标号处,跳到这个标号的两倍位置。例如当前位置标号为i,那么他可以一下子跳到2i处。但是这个技能有个特点,他将收到双倍伤害/生命。
例如i位置是陷阱,会对他造成10点伤害,那么小明施展这个技能跳到2i位置时,将受到20点伤害。反之,如果是血瓶,他将增加20点生命。
这条密道既充满着危险,也到处是机遇,小明想要在走出密道时收获最强大的生命力量!那么机智的你能否预算出小明能收获的最大的生命值呢?
前路充满风险和希望,奔跑吧,小明!

输入

数据有T组测试数据。
每组测试数据开始输入一个整数n,后面有n个整数(存在正负数)。正数表示血瓶,数值表示增加的生命值;负数表示陷阱,数值表示收到的伤害。
接下来输入一个整数q,表示q组询问。
每组询问由两个整数st和ed组成,分别代表初始位置和出口位置。

输出

每组询问输出一个数值,表示离开出口时小明能收获的最大生命值。
注意初始位置和出口位置造成的伤害或增加的生命值也要算进去。

样例输入

1
3
1 -2 3
1
1 3

样例输出

4

提示

样例解释:
密道长度为3。
分别是1,-2,3,即:
位置:    1  2     3
物品:血瓶(+1),陷阱(-2),血瓶(+3)。
小明出生在1位置,这时候他有4种选择,走一步,两步,三步,跳过去。
那么很显然,他可以绕过陷阱,直接走两步到达出口,即位置3。
此时可以收获4个生命力量,即最大生命值。

代码如下

#include <stdio.h>  
int a[1005],ed,ab;  
void jisuan(int st,int s)  
{  
    if(st==ed)ab=ab<s?s:ab;  
    else if(st<ed)  
    {  
        for(int j=0; j<4; j++)  
        {  
            if(j==0)jisuan(st+1,s+a[st+1]);  
            else if(j==1)jisuan(st+2,s+a[st+2]);  
            else if(j==2)jisuan(st+3,s+a[st+3]);  
            else if(j==3)jisuan(st*2,s+a[st]+a[st*2]);  
        }  
    }  
}  
int  main()  
{  
    int n;  
    scanf("%d",&n);  
    while(n--)  
    {  
        int m,q;  
        scanf("%d",&m);  
        for(int i=1; i<=m; i++)  
            scanf("%d",a+i);  
        scanf("%d",&q);  
        while(q--)  
        {  
            ab=-1005;  
            int st;  
            scanf("%d%d",&st,&ed);  
            jisuan(st,a[st]);  
            printf("%d
",ab);  
        }  
    }  
    return 0;  
}  

代码来源于互联网,仅供参考!