从起点到终点有N步，如果“走”第K步，将会得到A[K]元钱，A[K]可能为负数

更新时间2018-10-28 11:19:19

你也可以花100元钱“跳过”当前的这一步，即不会得到A[K]。但是任何时刻身上的钱都必须是非负的开始时，你身上共有0元。给定数组A，求在能到达终点的情况下最小需要走过（即不是用100元钱跳过）的步数。

注意：最后一步必须走，不能选择跳过。

输入

第一行为一个整数N。

第二行有N个整数，第K个数为A[K]。

输出

输出一个整数，表示需要走的最少步数。若无法走到终点，输出-1。

求这题c++代码，谢谢，很急！

#include <cstdio>#include <iostream>using namespace std;int f[101][101][2],n,a[101];int main()
{
   freopen("steps.in","r",stdin);
   freopen("steps.out","w",stdout);    scanf("%d",&n);    for (int q=1;q<=n;q++)     scanf("%d",&a[q]);    for (int i=1;i<=n;i++)     for (int j=0;j<=i;j++)
     f[i][j][0]=f[i][j][1]=-999999999;  //初始化
   for (int i=1;i<=n;i++)     for (int j=1;j<=i;j++)
    {         if (max(f[i-1][j][0],f[i-1][j][1])>=100&&i!=n) f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])-100;  //计算下一步跳剩余的钱数
        if (max(f[i-1][j-1][0],f[i-1][j-1][1])+a[i]>=0) f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1])+a[i];  //计算下一步走剩余的钱数
    }    for (int i=1;i<=n;i++)     if (f[n][i][1]>=0||f[n][i][0]>=0)
    {        printf("%d",i);  //输出答案
       return 0;
    }    printf("-1");  //无法到达输出“-1”
   return 0;
}