NCSTOJ-1500 : 魔法少女(动态规划)

太过爱你忘了你带给我的痛 2022-03-07 06:36 115阅读 0赞

# [1500 : 魔法少女][1500 _] #

### Description ###

魔法少女小圆要打倒站在N楼楼顶的女魔头

初始阶段小圆在地面上，相当于1楼楼底。

每层楼都有一个高度h，代表着小圆要爬当前层楼需要的时间为h。

小圆可以使用魔法（不花费时间）直接飞过1层楼或2层楼。但小圆每次使用过魔法后必须补充能量，下一层楼必须爬上去。换句话说，就是下层楼必须要花费时间。

对于样例的解释：

小圆使用魔法，到达2楼楼顶，不花费时间；

小圆爬到3楼楼顶，时间花费1；

小圆使用魔法，到达5楼楼顶，不花费时间，遇到女魔头。

### Input ###

输入包含多组数据，以文件输入结尾结束。

每组数据第一行一个数字N（1 ≤ N ≤ 10000），代表楼层数量。

接下来一行包含N个100以内的正整数，第i个数代表第i层楼的高度。

### Output ###

对于每组数据，输出一行，一个数字S，代表通往楼顶所需的最短时间。

### Sample Input ###

5
    3 5 1 8 4

### Sample Output ###

### dp动态规划 ###

可以设置dp\[i\]\[0\]表示在第i层楼顶没有能量，那这层一定是飞上来的，不花费时间  
，那可能是从第i-1层飞上来的也可能是从第i-2层飞上来的  
设置dp\[i\]\[1\]表示在第i层楼顶有能量，那这一层是爬上来的，花费时间，那第i-1层可能有能量也可能没有能量，也就是第i-1层爬的，或者第i-1层飞上去的。

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<unordered_set>
    #include<set>
    #include<unordered_map>
    #include<vector>
    #include<algorithm>
    #include<set>
    #include<queue>
    #include<cmath>
    using namespace std;
    int dp[10005][2]; //dp[i][0]表示这一层楼顶没有能量，不需要花时间
    int m[10005];     //dp[i][1]表示这一层楼顶有能量，需要花费时间来补充
    int main()
    { 
        int t;
        while(cin>>t)
        { 
            for(int i=1;i<=t;i++)
            { 
                cin>>m[i];
            }
            dp[1][1]=m[1];
            dp[2][1]=m[2];
            for(int i=3;i<=t;i++)
            { 
                dp[i][0]=min(dp[i-1][1],dp[i-2][1]);
                dp[i][1]=m[i]+min(dp[i-1][0],dp[i-1][1]);
            }
            cout<<min(dp[t][0],dp[t][1])<<endl;
        }
        return 0;
    
    }

[1500 _]: http://acm.ncst.edu.cn/problem.php?pid=1500