51nod 1344 走格子

Posted by kele on July 15, 2018

51nod 1344 走格子

也是比较简单的贪心算法,最喜欢这种比较简单的题目了2333

最优子结构性质:
走完前n个格子所需要的初始能量最小,等于走完前n-1个格子所需要的初始能量加上从第n-1个格子走到第n个格子所需要初始能量

贪心性质:
尽可能给最少的初始能量,所以只在能量为负数时,给初始能量,给得初始能量只能让机器人的能量给0,能够移动就可以了

代码:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    //int gezi[50005];
    int start=0,tmp,sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        sum+=tmp;
        if(sum<0)
        {
            start+=-sum;
            sum=0;
        }
    }
    cout<<start<<endl;
}