难度还好

这里只讲一下T4的做法

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

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

看到这题，很容易可以想起曾经做过的黑熊过河等题目。 因为后面的每一步都取决于曾经的走法结果，所以就更确定这题使用DP来做了。

My train to thought （我的思路）

首先这道题一共有两种走法：

runjump

所以就可以定义一个f[][][]数组；意思是什么呢 ？

f[i][j][0]表示从0格走到 i 格用 j 步后下一次跳剩余的钱数

f[i][j][1]表示从0格走到 i 格用 j 步后下一次走剩余的钱数

这样就很快的推出公式：

f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])-100; f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1])+a[i];

当然，各自还需要判断一下：

if(max(f[i-1][j][0],f[i-1][j][1])-100>=0&&i!=n)......//花费后还能撑住否？i==n否？ if(max(f[i-1][j-1][0],f[i-1][j-1][1])+a[i]>=0)...... //如果a[i]是负数有可能跳不了

最后搜索f [n] [1~n] [0~1]哪个成立 (非负的那个数是剩余钱数)

所以还有最重要的： f[][][]数组一开始要全部定义为负数

解析到此，有神马不会的可以私聊我哦

. . . . . . . . . . . . . . . . . . . . . . E N D . . . . . . . . . . . . . . . . . . . . . .